Cod sursa(job #574538)

Utilizator deneoAdrian Craciun deneo Data 7 aprilie 2011 11:45:03
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<fstream>
#include<deque>
using namespace std;

deque< pair<int, int> > v;
int n, k;

void insert(int a, int poz) {
	while(v[v.size()].first <  a)
		v.pop_back();
	v.push_back(make_pair(a, poz));
}

void update(int poz) {
	while(v[0].second < poz)
		v.pop_front();
}

int main() {
	int i, j, st, a, min;
	ifstream f("secventa.in");
	ofstream g("secventa.out");
	f >> n >> k;

	for(i = 1; i <= k; ++i) {
		f >> a;
		insert(a, i);
	}
	
	min = v[0].first;
	st = k;
	for(i = k + 1; i <= n; ++i) {
		f >> a;
		insert(a, i);
		update(i - k + 1);
		if(v[0].first > min) {
			min = v[0].first;
			st = i;
		}
	}
	g << st << ' ' << st - k + 1 << ' ' << min << '\n';
	g.close();
	return 0;
}