Cod sursa(job #2397995)

Utilizator FrostfireMagirescu Tudor Frostfire Data 4 aprilie 2019 22:56:43
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <iostream>

using namespace std;

ofstream g("secventa.out");

int n, k, v[500100], dq[500100], sol = -30100, p1, p2, p = 31999;
char buffer[32010];

void inc()
{
    p++;
    if(p==32000)
    {
        fread(buffer,1,32000,stdin);
        p=0;
    }
}

void read(int &x)
{
    int sgn = 1;
    while((buffer[p] < '0' || buffer[p] > '9') && buffer[p] != '-')
        inc();
    x = 0;
    if(buffer[p] == '-') sgn = -1, inc();
    while(buffer[p]>='0' && buffer[p]<='9')
    {
        x = 10 * x + buffer[p] - '0';
        inc();
    }
    x = x * sgn;
}

int main()
{
    freopen("secventa.in","r",stdin);
    read(n);
    read(k);
    for(int i=1; i<=n; i++)
        read(v[i]);
    int st = 1;
    int dr = 0;
    for(int i=1; i<=n; i++)
    {
        while(st <= dr && v[i] <= v[dq[dr]]) dr--;
        dq[++dr] = i;
        if(dq[st] == i-k) st++;
        if(i >= k && v[dq[st]] > sol)
        {
            p1 = i - k + 1;
            p2 = i;
            sol = v[dq[st]];
        }
    }
    g << p1 << ' ' << p2 << ' ' << sol << '\n';
    return 0;
}