Cod sursa(job #1202177)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 27 iunie 2014 10:46:21
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
using namespace std;
#include <fstream>
ifstream fin("secventa.in");
ofstream fout("secventa.out");

const int Kmax = 500000;
const int Nmax = 500000;

int v[Nmax+1];
int Q[Kmax+1], first = 0, last = -1;

void push(int) ;

int main()
{
    int i, k, n, a, MAX = -50000, x, y;
    fin >> n >> k;
    for(i = 1; i <= n; ++i) {fin >> v[i];}
    for(i = 1; i < k; ++i) push(i);
    for(i = k; i <= n; ++i)
    {
        push(i);
        a = v[ Q[first] ];
        if(a > MAX) MAX = a, x = 1+i-k, y = i;
        if(Q[first] == 1+i-k) ++first;
    }
    fout << x << ' ' << y << ' ' << MAX << '\n';
    return 0;
}


void push(int poz)
{
    while(first <= last && v[ Q[last] ] > v[poz]) --last;
    ++last;
    Q[last] = poz;
}