Cod sursa(job #1389306)

Utilizator MaarcellKurt Godel Maarcell Data 16 martie 2015 10:18:33
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <iostream>
#include <fstream>
using namespace std;

int N,K,a[500010],q[500010];

int main(){
    ifstream fin("secventa.in");
    ofstream fout("secventa.out");
    fin >> N >> K;

    int i,l=1,r=0,MAX=-(1<<30),ind;
    for (i=1; i<=N; i++) fin >> a[i];

    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]];
            }
    }

    fout << ind-K+1 << " " << ind << " " << MAX << "\n";
    return 0;
}