Cod sursa(job #1389364)

Utilizator MaarcellKurt Godel Maarcell Data 16 martie 2015 10:47:08
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
using namespace std;

int N,K,a[500010],q[500010]; char s[10000000];

int main(){
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d %d\n",&N,&K);
    fgets(s,10000000,stdin);

    int i,l=1,r=0,MAX=-(1<<30),ind,sgn=1,L=strlen(s),nr=0,t=0;
    s[L]=' ';

    for (i=0; i<=L; i++){
        if (s[i]=='-') sgn*=-1;
        else if (s[i]==' '){
            if (sgn==-1) nr*=-1;
            a[++t]=nr;
            nr=0;
            sgn=1;
        }
        else nr=nr*10+s[i]-'0';
    }


    for (i=1; i<=N; i++){
        q[++r]=i;

        while (r && q[l]<i-K+1) l++;
        while (r>l && a[q[r]]<=a[q[r-1]]) q[r-1]=q[r],r--;

        if (i>=K)
            if (MAX<a[q[l]]){
                ind=i;
                MAX=a[q[l]];
            }
    }

    printf("%d %d %d\n",ind-K+1,ind,MAX);
    return 0;
}