Cod sursa(job #2447191)

Utilizator ElizaTElla Rose ElizaT Data 12 august 2019 13:15:56
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;

int a[500005],q[500005];

int main()
{
    ifstream fin("secventa.in");
    ofstream fout("secventa.out");
    int n,k,st = 1,dr = 0,ans = -30000000,poz;
    fin >> n >> k;
    for (int i = 1;i<= n;i++)
        fin >> a[i];
    for (int i = 1;i < k;i++) {
        while(dr >= st && a[i] <= a[q[dr]])
            dr--;
        dr++;
        q[dr] = i;
    }
    for (int i = k;i <= n;i++) {
        while(st <= dr && a[i] <= a[q[dr]])
            dr--;
        dr++;
        q[dr] = i;
        while (st <= dr && q[st] < i - k + 1)
            st++;
        if (a[q[st]] > ans) {
            ans = a[q[st]];
            poz = i;
        }
    }
    fout << poz - k + 1 << " " << poz << " " << ans;
    return 0;
}