Cod sursa(job #2807960)

Utilizator andrei81Ragman Andrei andrei81 Data 24 noiembrie 2021 13:14:57
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <iostream>
#include <queue>

using namespace std;

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

FILE* fin, * fout;

const int DIM = 4096;
int pos = DIM - 1;
char buffer[DIM];

char read_char()
{
    pos++;
    if ( pos == DIM )
    {
        pos = 0;
        fread(buffer, 1, DIM, stdin);
    }
    return buffer[pos];
}

int readnr()
{
    int nr = 0, sign = 1;
    char ch = read_char();

    while ( !((ch >= '0' && ch <= '9') || ch == '-') )
        ch = read_char();

    if ( ch == '-' )
    {
        sign = -1;
        ch = read_char();
    }

    while ( ch >= '0' && ch <= '9' )
    {
        nr = nr * 10 + (ch - '0');
        ch = read_char();
    }

    return nr * sign;
}

int main()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);

    n = readnr();
    k = readnr();


    maxx = -9999999;
    poz = 1;

    for ( int i = 1; i <= n; i++ )
        v[i] = readnr();


    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;
        }
    }

    cout << poz << " " << poz + k - 1 << " " << maxx;
}