Cod sursa(job #1908789)

Utilizator NinjaCubeMihai Radovici NinjaCube Data 7 martie 2017 10:27:47
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <cctype>
using namespace std;

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

const int MAXN = 500005;

int n,k;
int v[MAXN];
int prasp,qrasp,bazarasp;
int Deque[MAXN];
int p,q;

char buffer[MAXN * 6 * 2];//(numere de 5 cifre + 1 minus) * 2 pentru ca sunt spatii

void citire()
{
    in >> n >> k;
    in.ignore();
    in.getline(buffer, MAXN * 6 * 2 - 1);
    int poz = 0;
    for (int i = 1;i <= n;++i,++poz)
    {
        int semn = 1;
        if (buffer[poz] == '-')
        {
            semn = -semn;
            ++poz;
        }
        while(isdigit(buffer[poz]))
        {
            v[i] = v[i] * 10 + buffer[poz] - '0';
            ++poz;
        }
        v[i] *= semn;
    }
}

void prelucrare()
{
    p = 1, q = 0;
    for (int i = 1;i <= k;++i)
    {
        while(p <= q && v[Deque[q]] >= v[i])
            --q;
        Deque[++q] = i;
    }
    bazarasp = v[Deque[p]];
    prasp = 1;
    qrasp = k;
    for (int i = 2;i <= n - k + 1;++i)
    {
        if (Deque[p] <= i - 1)
            ++p;
        while(p <= q && v[Deque[q]] >= v[i + k - 1])
            --q;
        Deque[++q] = i + k - 1;
        if (v[Deque[p]] > bazarasp)
        {
            bazarasp = v[Deque[p]];
            prasp = i;
            qrasp = i + k - 1;
        }
    }
}

int main()
{
    citire();
    prelucrare();
    out << prasp << ' ' << qrasp << ' ' << bazarasp << '\n';
    return 0;
}