Cod sursa(job #2146964)

Utilizator bogdi1bogdan bancuta bogdi1 Data 28 februarie 2018 12:49:55
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
deque<int> dq;
int v[500005];
int main()
{   freopen("secventa.in", "r",stdin);
    freopen("secventa.out", "w",stdout);
    int n,k,i,maxx,st,dr;
    scanf("%d%d", &n, &k);
    scanf("%d", &v[1]);
    dq.push_back(1);
    for(i=2; i<=k; i++){
        scanf("%d", &v[i]);
        while(!dq.empty() && v[dq.back()]>v[i])
            dq.pop_back();
        dq.push_back(i);
    }
    maxx=v[dq.front()];
    for(i=k+1; i<=n; i++){
        scanf("%d", &v[i]);
        while(!dq.empty() && v[dq.back()]>=v[i])
            dq.pop_back();
        while(!dq.empty() && dq.front()<=i-k)
            dq.pop_front();
        dq.push_back(i);
        if(maxx<v[dq.front()]){
            maxx=v[dq.front()];
            st=i-k+1;
            dr=i;
        }
    }
    printf("%d %d %d", st, dr, maxx);
    return 0;
}