Cod sursa(job #1144753)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 17 martie 2014 15:45:23
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<fstream>
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");

const int nmax = 500005;
int d[nmax], p = 1, q = 0, maxim, bestbeg, bestend, n, k, v[nmax], nr;

int main(){
	int player_unu=0;

	in>>n>>k;
	for(int i = 1; i<=n; i++)
	{
		in>>v[i];

		while(v[d[q]]>v[i] && p<=q)
			q--;

		q++;
		d[q] = i;

		while (i-nr>k) {
            nr++;
            if (nr==d[p])
                p++;
        }
        if (i-nr==k) {
            if (maxim < v[d[p]]) {
                maxim=v[d[p]];
                bestbeg=nr+1;
                bestend=i;
            }
        }
	}

	out<<bestbeg<<" "<<bestend<<" "<<maxim<<'\n';
	return player_unu;
}