Cod sursa(job #512856)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 14 decembrie 2010 18:22:27
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<iostream>
#include<fstream>
using namespace std;
const int N=500001;
int a,s,smax,dr,st=1,d[N],v[N],n,k;
void stanga (int i) {
	while ((i-d[st]>=k) && (v[d[st]]<v[d[st+1]])) {
		++st;
	}
}

void dreapta (int i) {
	while (st<=dr && v[d[dr]]>=v[i]) {
		--dr;
	}
}

void adauga (int i) {
	d[++dr]=i;
}

ifstream aa("secventa.in");
ofstream ss("secventa.out");
int main () {
	int i;
	aa >> n >> k;
	for (i=1;i<=n;++i) {
		aa >> v[i];
		stanga(i);
		dreapta(i);
		adauga(i);
		if (d[st]>smax) {
			smax=v[d[st]];
			a=i-k+1;
			s=i;
		}
	}
	ss << a << " " << s << " " << smax; 
	return 0;
}