Cod sursa(job #2770503)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 21 august 2021 14:35:55
Problema Secventa Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
//Ilie Dumitru
#include<cstdio>

int v[500000];
int dq[500000], begin=0, end=0;

int main()
{
    int N, K, i, min, start;
    FILE *f=fopen("secventa.in", "r"), *g=fopen("secventa.out", "w");
    fscanf(f, "%d%d", &N, &K);
    for(i=0;i<K;++i)
    {
        fscanf(f, "%d", v+i);
        while(begin<end && v[dq[end-1]]>=v[i])
            --end;
        dq[end++]=i;
    }
    min=v[*dq];
    start=0;
    for(;i<N;++i)
    {
        fscanf(f, "%d", v+i);
        while(begin<end && v[dq[end-1]]>=v[i])
            --end;
        while(begin<end && i-dq[begin]>=K)
            ++begin;
        dq[end++]=i;
        if(v[dq[begin]]>min)
        {
            min=v[dq[begin]];
            start=i-K+1;
        }
    }
    fprintf(g, "%d %d %d", start+1, start+K, min);
    fclose(g);
    fclose(f);
    return 0;
}