Cod sursa(job #2204585)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 16 mai 2018 17:27:21
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <cstdio>
#include <algorithm>

using namespace std;

FILE *f = fopen("secventa.in","r");
FILE *g = fopen("secventa.out","w");

int N,K;
int V[500005];
int D[500005],stq,drq;
int ma = -3000000,ind;

int main(){
    fscanf(f,"%d %d",&N,&K);
    for(int i = 1;i <= N;i++){
        fscanf(f,"%d",&V[i]);
    }

    stq = 1;drq = 0;
    for(int i = 1;i <= N;i++){
        while(stq <= drq && D[stq] <= i - K){
            stq++;
        }
        while(stq <= drq && V[D[drq]] > V[i]){
            drq--;
        }
        D[++drq] = i;
        if(i >= K && V[D[stq]] > ma){
            ma = V[D[stq]];
            ind = i - K + 1;
        }
    }

    fprintf(g,"%d %d %d",ind,ind + K - 1,ma);
    fclose(f);
    fclose(g);

    return 0;
}