Cod sursa(job #2140035)

Utilizator VladAfrasineiAfrasinei VladAfrasinei Data 22 februarie 2018 23:13:50
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int n,k,a[500005];
deque <int> q;
int maxi,l;
int main()
{
    int i;
fin>>n>>k;
for(i=1;i<=n;i++)
    fin>>a[i];
for(i=1;i<=k;i++)
{
    while(!q.empty()&&a[i]<a[q.back()])
        q.pop_back();
    q.push_back(i);
}
maxi=a[q.front()];
l=k;
for(i=k+1;i<=n;i++)
{
    while(!q.empty()&&a[i]<a[q.back()])
        q.pop_back();
    q.push_back(i);
    while(!q.empty()&&q.front()<i-k+1)
        q.pop_front();
    if(a[q.front()]>maxi)
    {
        maxi=a[q.front()];
        l=i;
    }
}
fout<<l-k+1<<" "<<l<<" "<<maxi;
    return 0;
}