Cod sursa(job #811833)

Utilizator BalcauIonutFMI-Balcau Ionut BalcauIonut Data 12 noiembrie 2012 23:18:01
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
#include<deque>
#include<sstream>
using namespace std;

stringstream ss;
char str[3000000];
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;
    fin.getline(str,3000000);
    ss<<str;
    for(i=1;i<=k;++i){
        ss>>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){
         ss>>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;
}