Cod sursa(job #1181907)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 4 mai 2014 10:58:23
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<fstream>
#include<iostream>
#define nmax 500009
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");
int sol = -40000,v[nmax],deq[nmax],k,front,back,n,x1,x2,x3;

int main()
{

    in>>n>>k;
    int i;
    for(i = 1 ; i <= n ; i++)
        in>>v[i];
    front = 1;
    back = 0;
    for(i = 1 ; i <= n ; i++)
    {
        x3 = deq[back]-1;
        while(front <= back && v[i] <= v[deq[back]])
            --back;
        deq[++back] = i;
        if(deq[front] == i-k) front++;
        if(deq[front] >= k) {
            if(v[deq[front]] > sol){
                sol = v[deq[front]];
                 x1 = x3;
                 x2 = deq[front];
            }
        }
    }

    out<<x1<<" "<<x2<<" "<<sol;
    out.close();
    in.close();
    return 0;
}