Cod sursa(job #811814)

Utilizator BalcauIonutFMI-Balcau Ionut BalcauIonut Data 12 noiembrie 2012 22:38:06
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<fstream>
#include<deque>
using namespace std;


int main(){
    short int a[500001];
    deque<int> q;
    int s=-(1<<30),mn=0,i,k,n;
    ifstream fin("secventa.in");
    fin>>n>>k;
    for(i=1;i<=k;++i){
        fin>>a[i];
        while(!q.empty() && a[i]<a[q.back()])
            q.pop_back();
        q.push_back(i);
    }
        s=a[q.front()]; mn=q.front();
    for(i=k+1;i<=n;++i){
         fin>>a[i];
         if(q.front()==i-k)
            q.pop_front();

        while(!q.empty() && a[i]<a[q.back()])
            q.pop_back();
        q.push_back(i);

        if(a[q.front()]>s){
        s=a[q.front()]; mn=q.front();
        }
    }
    int kmn=mn;
    for( ;mn>0 && a[--mn]>=s; );
    ++mn;
    while(kmn-mn<k-1 && kmn<n) ++kmn;
    ofstream fout("secventa.out");
    fout<<mn<<' '<<kmn<<' '<<s;
return 0;
}