Cod sursa(job #1675286)

Utilizator serbanSlincu Serban serban Data 5 aprilie 2016 11:10:32
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>

#define pii pair<int, int>

using namespace std;

pii q[500005];
int l = 1;

int main()
{
    ifstream f("secventa.in");
    ofstream g("secventa.out");
    int n, k, x, st, dr, mx = -30005;
    f >> n >> k;
    for(int i = 1; i < k; i ++) {
        f >> x;
        while(q[0].first >= l && q[q[0].first].first > x)
            q[0].first --;
        q[++ q[0].first] = {x, i};
    }
    for(int i = k; i <= n; i ++) {
        f >> x;
        while(q[0].first >= l && q[q[0].first].first > x)
            q[0].first --;
        q[++ q[0].first] = {x, i};

        int aux = q[l].second;
        while(q[q[0].first].second - q[l].second >= k && q[l].second < q[l + 1].second)
            l ++;
        if(mx < q[l].first) {
            mx = q[l].first;
            st = i - k + 1;
            dr = i;
        }
    }
    g << st << " " << dr << " " << mx << "\n";
    return 0;
}