Cod sursa(job #1097910)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 4 februarie 2014 10:45:30
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <deque>
#include <cstring>

using namespace std;

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

const int Nmax = 5e5 + 100;
const int Smax = 2e6;
const int oo = 0x3f3f3f3f;

struct Poz_Val{
    int p, v;
}E;

int N, K, V[Nmax];
deque <Poz_Val> D;

int Number(char* p)
{
    int sign = 1, i = 0, nr = 0;
    if(p[0] == '-') sign = -1, i++;
    for(; i < strlen(p); i++)
        nr = nr * 10 + p[i] - '0';
    return sign * nr;
}

void Read()
{
    fin.get();
    char s[Smax]; int nr = 1;
    fin.getline(s, Smax);
    char *p = strtok(s, " ");
    V[nr] = Number(p);
    while(p = strtok(NULL, " "))
        V[++nr] = Number(p);
}

int main()
{
    fin >> N >> K;
    Read();

    E.v = V[1]; E.p = 1;
    D.push_back(E);

    for(int i = 2; i <= K; i++)
    {
        E.v = V[i]; E.p = i;
        while(D.size() && D.back().v >= E.v)
            D.pop_back();
        D.push_back(E);
    }

    int best = D.front().v, st = 1, dr = K;
    for(int i = K + 1; i <= N; i++)
    {
        E.v = V[i]; E.p = i;
        while(D.size() && D.back().v >= E.v)
            D.pop_back();
        D.push_back(E);
        if(D.front().p <= i - K)
            D.pop_front();
        if(best < D.front().v)
        {
            best = D.front().v;
            st = i - K + 1; dr = i;
        }
    }

    fout << st << ' ' << dr << ' ' << best;
    return 0;
}