Cod sursa(job #1455378)

Utilizator GilgodRobert B Gilgod Data 27 iunie 2015 20:40:50
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <assert.h>
#include <list>

#define mkpair(a,b) std::make_pair((a),(b))
#define tuple std::pair<int,int>

const char IN[] = "secventa.in", OUT[] = "secventa.out";
const int NMAX = 500000;
const int INF = 0x3f3f3f3f;



using namespace std;

int K, N;

inline void read_data() {
	assert(freopen(IN, "r", stdin));
	assert(scanf("%d %d", &N, &K));
	int best = -INF, best_start = -1, best_end = -1;
	list<tuple> deq;
	for (int i = 0; i < N; ++i) {
		int x;
		assert(scanf("%d", &x));
		while (!deq.empty() && deq.back().first >= x) {
			deq.pop_back();
		}
		while (!deq.empty() && i - deq.front().second >= K) {
			deq.pop_front();
		}
		deq.push_back(mkpair(x, i));
		if (i >= K - 1) {
			if (deq.front().first > best) {
				best = deq.front().first;
				best_start = i - K + 1;
				best_end = i;
			}
		}
	}
	fprintf(fopen(OUT, "w"), "%d %d %d\n", best_start + 1, best_end + 1, best);
	fclose(stdin);
}

int main() {
	read_data();
	return 0;
}