Cod sursa(job #1455389)

Utilizator GilgodRobert B Gilgod Data 27 iunie 2015 21:16:29
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 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;
const int BUFLEN = (1 << 12);


using namespace std;

int K, N;
tuple deq[NMAX];
int head = -1, tail = -1;
char buff[BUFLEN];
int counter = BUFLEN-1;

inline void read(int &x) {
	x = 0;
	int sgn = 0;
	while (!(buff[counter] >= '0' && buff[counter] <= '9' || buff[counter] == '-'))
		if (++counter == BUFLEN)
			fread(buff, 1, BUFLEN, stdin), counter = 0;
	do {
		if (buff[counter] == '-') sgn = 1;
		else x = (x << 3) + (x << 1) + (buff[counter] - '0');
		if (++counter == BUFLEN) 
			fread(buff, 1, BUFLEN, stdin), counter = 0;
	} while (buff[counter] >= '0' && buff[counter] <= '9');
	if (sgn) x = -x;
}

inline void read_data() {
	assert(freopen(IN, "r", stdin));
	read(N);
	read(K);
	int best = -INF, best_start = -1, best_end = -1;
	
	for (int i = 0; i < N; ++i) {
		int x;
		read(x);
		while (tail != -1 && deq[tail].first >= x) {
			--tail;
		}
		while (head != -1 && i - deq[head].second >= K) {
			++head;
		}
		if (head > tail) head = tail = -1;
		deq[++tail] = mkpair(x, i);
		if (head == -1) head = 0;
		if (i >= K - 1) {
			if (deq[head].first > best) {
				best = deq[head].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;
}