Cod sursa(job #1719561)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 19 iunie 2016 16:15:56
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 500005;

struct PII {
    int x, y;

    inline PII() { }
    inline PII(int _x, int _y) {
        x = _x;
        y = _y;
    }
};

int v[NMAX];

int main(void) {
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    int n, k, st, dr, a, b, ans;
    deque<PII> dq;


    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; ++i)
        scanf("%d",&v[i]);

    for(st=dr=1; dr<=k; ++dr) {
        while(!dq.empty() && v[dr]<dq.back().x)
            dq.pop_back();
        dq.push_back(PII(v[dr], dr));
    }

    a = 1;
    b = k;
    ans = dq.front().x;

    for(++st; dr<=n; ++dr) {
        while(!dq.empty() && dr-dq.front().y>=k)
            dq.pop_front();
        while(!dq.empty() && v[dr]<=dq.back().x)
            dq.pop_back();

        dq.push_back(PII(v[dr], dr));

        if(dq.front().x>ans) {
            a   = dr-k+1;
            b   = dr;
            ans = dq.front().x;
        }
    }

    printf("%d %d %d\n",a,b,ans);

    fclose(stdin);
    fclose(stdout);
    return 0;
}