Cod sursa(job #547723)

Utilizator cristian9Cristian Zloteanu cristian9 Data 6 martie 2011 17:34:43
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
//#include<stdio.h>
#include<fstream>
using namespace std;
int deque[500001], v[500001];

int main(){
    //freopen ("secventa.in", "r", stdin);
    //freopen ("secventa.out", "w", stdout);
    ifstream f ("secventa.in");
    ofstream w ("secventa.out");
    int n, i, k, max=-500000, x;

    //scanf("%d %d ", &n, &k);
    f>>n>>k;

    for(i=1; i<=n; i++)
        //scanf("%d ", &v[i]);
        f>>v[i];

    int front=1, back=0;

    for(i=1; i<=n; i++){
        while(front<=back && v[i]<=v[deque[back]])
            back--;
        deque[++back]=i;
        while(front<=back && i-k>=deque[front]){
            front++;
        }
        if(v[deque[front]]>max && i>=k){
            max=v[deque[front]];
            x=i;
        }
    }

    //printf("%d %d %d\n", x-k+1, x, max);
    w<<x-k+1<<" "<<x<<" "<<max;
    return 0;
}