Cod sursa(job #1481428)

Utilizator CalinSpiridonSpiridon Calin CalinSpiridon Data 4 septembrie 2015 14:23:52
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int n, k, m, cc, sign, nr;
int a[500010];
int deque[500010];
char c[3000100];


int main(){
    fin>>n>>k;
    int ct=0;
    sign=1;
    // citire parsata
    fin.get();
    fin.get(c , 3000010);
    for(int i=0; c[i]!=0; ++i){
        if(c[i]=='-') sign=-1;
        if(c[i]>='0' && c[i]<='9'){
            nr=nr*10+(c[i]-'0');
        }
        if(c[i]==' '){
            a[++ct]=nr*sign;
            sign=1;
            nr=0;
        }
    }
    a[++ct]=nr*sign;

    int back=0;
    int front=1;
    int mx=-30001;
    for(int i=1;i<=n;++i){
        while(front<=back && a[i]<=a[deque[back]]) back--;
        deque[++back]=i;
        if(deque[front]==i-k) ++front;
        if(i>=k){
            m=a[deque[front]];
            if(m>mx){
                cc=i-k+1;
                mx=m;
            }
        }
    }
    fout<<cc<<' '<<cc+k-1<<' '<<mx;


    return 0;
}