Cod sursa(job #1604136)

Utilizator aimrdlAndrei mrdl aimrdl Data 17 februarie 2016 23:34:03
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <list>
#include <string.h>

using namespace std;

struct item {
	int val;
	int pos;
};

inline void read (int *v) {
	static char buffer[1024];
	fgets(buffer, 1024, stdin);
	
	*v = 0;
	for (int i = 0; buffer[i] >= '0' && buffer[i] <= '9'; ++i) {
		*v = (*v) * 10 + (buffer[i] - '0');
	}
}

int main (void) {	
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	
	char buffer[1024];
	fgets(buffer, 1024, stdin);
	
	int n = 0, k = 0;
	
	int i;
	for (i = 0; buffer[i] >= '0' && buffer[i] <= '9'; ++i) {
		n = n * 10 + (buffer[i] - '0');
	}
	
	for (++i; buffer[i] >= '0' && buffer[i] <= '9'; ++i) {
		k = k * 10 + (buffer[i] - '0');
	}
	
	int v[n];
	
	list<item> l;
	
	item aux;
	int max = 0, startSol = 0;
	
	for (int i = 0; i < k; ++i) {
		read(&v[i]);
		while (!l.empty() && v[i] <= l.back().val) {
			l.pop_back();
		}
		
		aux.val = v[i];
		aux.pos = i;
		l.push_back(aux);
	}
		
		
	max = l.front().val;
	startSol = l.front().pos;
	
	for (int i = k; i < n; ++i) {	
		read(&v[i]);
		while (!l.empty() && v[i] <= l.back().val) {
			l.pop_back();
		}
		
		aux.val = v[i];
		aux.pos = i;
		l.push_back(aux);
		
		if (l.front().pos <= i - k) l.pop_front();
		
		if (l.front().val > max) {
			max = l.front().val;
			startSol = l.front().pos;
		}
	}
	
	while (startSol && v[startSol] >= max) --startSol;
	if (v[startSol] < max) ++startSol;	
	
	printf("%d %d %d", startSol + 1, startSol + k, max);
	return 0;
}