Cod sursa(job #1632005)

Utilizator AureliaCretu Aurelia Aurelia Data 5 martie 2016 20:51:58
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

long int n, k, i, a[500001], maxi=-100000000000000, max1, max2;
deque <int> d;
ifstream f("secventa.in");
ofstream g("secventa.out");

int main()
{f>>n>>k;
for(i=1; i<=n; ++i) f>>a[i];
for(i=1; i<=n; ++i)
{
    while(d.size() && a[d.back()]>a[i]) d.pop_back();
    d.push_back(i);
    while(d.size() && i-k>=d.front()) d.pop_front();
    if(i>=k)
      if(a[d.front()]>=maxi)
        {maxi=a[d.front()];
        max1=i-k+1;
        max2=i;}
}
g<<max1<<" "<<max2<<" "<<maxi;
g.close();
f.close();
return 0;
}