Cod sursa(job #1719563)

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

const int NMAX = 500005;

struct PII {
    int x, y;
};

int v[NMAX];

int main(void) {
    ifstream f("secventa.in");
    ofstream g("secventa.out");

    int n, k, st, dr, a, b, ans;
    deque<PII> dq;


    f>>n>>k;
    for(int i=1; i<=n; ++i)
        f>>v[i];

    for(st=dr=1; dr<=k; ++dr) {
        while(!dq.empty() && v[dr]<dq.back().x)
            dq.pop_back();
        dq.push_back({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({v[dr], dr});

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

    g<<a<<' '<<b<<' '<<ans<<' '<<'\n';

    f.close();
    g.close();
    return 0;
}