Cod sursa(job #2172994)

Utilizator marcdariaDaria Marc marcdaria Data 15 martie 2018 19:40:03
Problema Secventa Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int N, K, p, v;
deque<pair<int, int>> DQ;

void Read();
void Get(int& x);

int main()
{
    Read();

    fout << p - K + 1 << " " << p << " " << v;

    fout.close();
    return 0;
}

const int Lim = 100000;
int p1 = Lim - 1;
char s[Lim];

void Next()
{
    if(++p1 == Lim)
        fin.get(s, Lim + 1, EOF), p1 = 0;
}

void Get(int& x)
{
    while(s[p1] < '0' || s[p1] > '9')
    {
        if(s[p1] == '-')
            break;
        Next();
    }

    int sgn = 1;
    if(s[p1] == '-')
    {
        sgn = -1;
        Next();
    }

    for(x = 0; s[p1] >= '0' && s[p1] <= '9'; Next())
        x = x * 10 + s[p1] - '0';
    x *= sgn;
}
void Read()
{
    Get(N); Get(K);

    int i, aux;
    for(i = 1; i <= K; ++i)
    {
        Get(aux);
        while(!DQ.empty() && DQ.front().first > aux)
            DQ.pop_front();

        DQ.push_front({aux, i});
    }

    v = DQ.back().first;
    p = K;

    for(i = K + 1; i <= N; ++i)
    {
        if(i - DQ.back().second >= K)
            DQ.pop_back();

        Get(aux);
        while(!DQ.empty() && DQ.front().first > aux)
            DQ.pop_front();

        DQ.push_front({aux, i});

        if(DQ.back().first > v)
        {
            v = DQ.back().first;
            p = i;
        }
    }
}