Cod sursa(job #593676)

Utilizator deneoAdrian Craciun deneo Data 4 iunie 2011 10:53:56
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<cstdio>
#include<deque>
using namespace std;

#define mk make_pair

int n, k, v[500001];
deque< pair<int, int> > d;

void insert(int p) {
	while(d.size() > 0 && d[d.size() - 1] . first >= v[p])
		d.pop_back();
	d.push_back( mk(v[p], p) );
}

int getmin(int st) {
	while(d.size() > 0 && d[0] . second < st)
		d.pop_front();
	return d[0].first;
}

int main() {
	int i, min, poz;
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	scanf("%d%d", &n, &k);
	for(i = 1; i <= n; ++i)
		scanf("%d", &v[i]);
	
	for(i = 1; i <= k; ++i)
		insert(i);
	
	poz = 1; 
	min = getmin(1);
	
	for(i = k + 1; i <= n; ++i) {
		insert(i);
		if(getmin(i - k + 1) > min) {
			min = getmin(i - k + 1);
			poz = i - k + 1;
		}
	}
	
	printf("%d %d %d\n", poz, poz + k - 1, min);
	
	return 0;
}