Cod sursa(job #2807918)

Utilizator andrei81Ragman Andrei andrei81 Data 24 noiembrie 2021 12:44:10
Problema Secventa Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <queue>

using namespace std;

int n, k, maxx, v[500005], poz;
deque<int> dq;

FILE* fin, * fout;
int main()
{
    fin = fopen("secventa.in", "r");
    fout = fopen("secventa.out", "w");

    fscanf(fin, "%d %d", &n, &k);

    maxx = -9999999;
    poz = 1;

    for ( int i = 1; i <= n; i++ )
        fscanf(fin, "%d", &v[i]);

    for ( int i = 1; i <= n; i++ )
    {
        while ( !dq.empty() && (dq.front() + k) <= i )
            dq.pop_front();

        while ( !dq.empty() && v[dq.back()] >= v[i] )
            dq.pop_back();

        dq.push_back(i);

        if ( i >= k && v[dq.front()] > maxx )
        {
            maxx = v[dq.front()];
            poz = i - k + 1;
        }
    }

    // fout << poz << " " << poz + k - 1 << " " << maxx;
    fprintf(fout, "%d %d %d", poz, poz + k - 1, maxx);
}