Cod sursa(job #565678)

Utilizator SadmannCornigeanu Calin Sadmann Data 28 martie 2011 09:38:42
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<fstream>
#include<deque>
#define NMAX 500001
#define INF -(1<<17)
using namespace std;
int N,K;
ifstream in("secventa.in");
ofstream out("secventa.out");
int V[NMAX],back=0,front=1;
deque<int> myDeque;

int main()
{
    in>>N>>K;
    int minim=INF;
    pair<int,int> pos;
    for(int i=1;i<=N;i++)
    {
        in>>V[i];
        while(!myDeque.empty() && V[myDeque.back()]>=V[i])
            myDeque.pop_back();
        myDeque.push_back(i);
        if(myDeque.front()==i-K)
            myDeque.pop_front();
        if(minim<V[myDeque.front()] && i>=K)
        {
            minim=V[myDeque.front()];
            pos=make_pair(i-K+1,i);
        }
    }

    out<<pos.first<<' '<<pos.second<<' '<<minim<<'\n';

    return 0;
}