Cod sursa(job #2038131)

Utilizator ruxi.icleanuRuxandra Icleanu ruxi.icleanu Data 13 octombrie 2017 11:34:20
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdlib.h>
#include <stdio.h>
#include <deque>

using namespace std;

#define MAXN 500000
#define INF 30001

int v[MAXN];
deque <int> deq;

FILE *fi, *fo;

inline int read_nr() {
    char ch;
    int nr=0, sgn=1;
    ch=fgetc(fi);
    if(ch=='-')
        sgn=-1;
    else
        nr=ch-'0';
    ch=fgetc(fi);
    while(ch>='0' && ch<='9') {
        nr=nr*10+(ch-'0');
        ch=fgetc(fi);
    }
    return nr*sgn;
}

int main()
{
    int n, k, i, poz_sf, bmax;
    fi = fopen("secventa.in", "r");
    fo = fopen("secventa.out", "w");
    n=read_nr();
    k=read_nr();
    for(i=0; i<n; i++)
        v[i]=read_nr();
    bmax=-INF;
    for(i=0; i<n; i++) {
        while(deq.empty()!=1 && v[i]<v[deq.back()])
            deq.pop_back();
        deq.push_back(i);
        if(i-deq.front()>=k) {
            deq.pop_front();
        }
        if(i>=k-1)
            if(v[deq.front()]>bmax) {
                bmax=v[deq.front()];
                //poz_in=deq.front();
                poz_sf=i;
            }
    }
    fprintf(fo, "%d %d %d", poz_sf-k+2, poz_sf+1, bmax);
    fclose(fi);
    fclose(fo);
    return 0;
}