Cod sursa(job #1097898)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 4 februarie 2014 10:35:37
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <deque>

using namespace std;

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

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

struct Poz_Val{
    int p, v;
}E;

int N, K;
deque <Poz_Val> D;

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

    fin >> E.v; E.p = 1;
    D.push_back(E);

    for(int i = 2; i <= K; i++)
    {
        fin >> E.v; 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++)
    {
        fin >> E.v; 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;
}