Cod sursa(job #1226552)

Utilizator harababurelPuscas Sergiu harababurel Data 6 septembrie 2014 03:46:48
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <iostream>
#include <fstream>
#include <deque>
#define nmax 500005
using namespace std;

int n, k, l, r, sol=-nmax, v[nmax];
deque <int> D;

int main() {
	ifstream f("secventa.in");
	ofstream g("secventa.out");

	f>>n>>k;
	for(int i=1; i<k; i++) {
			f>>v[i];
			while(!D.empty() && v[D.back()] >= v[i]) D.pop_back();
			D.push_back(i);
	}

	for(int i=k; i<=n; i++) {
			f>>v[i];
			while(!D.empty() && v[D.back()] >= v[i]) D.pop_back();
			D.push_back(i);

			if(D.front() + k <= i) D.pop_front();

			if(v[D.front()] > sol) {
				sol = v[D.front()];
				r = i;
			}
	}

	l = r;
	while(l>1 && v[l-1] >= sol) l--;

	g<<l<<" "<<r<<" "<<sol<<"\n";
	return 0;
}