Cod sursa(job #2770499)

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

int v[500000];
std::deque<int> dq;

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(!dq.empty() && v[dq.front()]>=v[i])
            dq.pop_front();
        dq.push_front(i);
    }
    min=v[dq.back()];
    start=0;
    for(;i<N;++i)
    {
        fscanf(f, "%d", v+i);
        while(!dq.empty() && v[dq.front()]>=v[i])
            dq.pop_front();
        while(!dq.empty() && i-dq.back()>=K)
            dq.pop_back();
        dq.push_front(i);
        if(v[dq.back()]>min)
        {
            min=v[dq.back()];
            start=i-K+1;
        }
    }
    fprintf(g, "%d %d %d", start+1, start+K, min);
    fclose(g);
    fclose(f);
    return 0;
}