Cod sursa(job #504792)

Utilizator mraresMardare Rares mrares Data 28 noiembrie 2010 18:36:36
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>
#include <fstream>
#define nmax 5000000
#define inf -10

using namespace std;

//FILE *fin=fopen("secventa.in", "r");
//FILE *fout=fopen("secventa.out", "w");

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

int v[nmax], deque[nmax];
int front, back, n, k, maxim, pozi, pozj;

int main()
{
    int i;
    maxim = inf;
    fin >> n >> k;
    //fscanf(fin, "%d%d", &n, &k);
    for(i=1; i<=n; ++i)
        fin >> v[i];

    front = 1;
    for(i=1; i<=n; ++i)
    {
        //fscanf(fin, "%d", &v[i]);
        while(front<=back && (v[i]<=v[deque[back]] || i-deque[back]>=k)) --back;
        deque[++back] = i;

        while(front<=back && i-deque[front]>=k) ++front;
        if(i>=k)
            if(maxim<v[deque[front]])
            {
                maxim=v[deque[front]];
                pozi = i-k+1;
                pozj = pozi+k-1;
            }
    }
    fout << pozi << " " << pozj << " " << maxim;
    //fprintf(fout, "%d %d %d", pozi,  pozj, maxim);
}