Cod sursa(job #357436)

Utilizator csizMocanu Calin csiz Data 19 octombrie 2009 11:55:50
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <queue>

using namespace std;

int main(){
    ifstream in("secventa.in");
    ofstream out("secventa.out");

    int n,k;in>>n>>k;
    deque<pair<int,int> > q;

    for(int i=0;i<k;i++){
        int x;in>>x;
        while(!q.empty()&&q.back().first>x) q.pop_back();
        q.push_back(make_pair(x,i));
    }
    int max=-30001;
    int s,f;
    for(int i=k;i<n;i++){
        if(q.front().first>max) {max=q.front().first;f=i;s=i-k+1;}
        if(q.front().second<=i-k) q.pop_front();
        int x;in>>x;
        while(!q.empty()&&q.back().first>x) q.pop_back();
        q.push_back(make_pair(x,i));
    }
    if(q.front().first>max) {max=q.front().first;f=n;s=n-k+1;}
    out<<s<<" "<<f<<" "<<max;
}