Cod sursa(job #2033797)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 7 octombrie 2017 10:46:53
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 500005
#define BUFF_MAX 500005

int n, k, a[NMAX];
deque<int> deq;
int baza_max = -0x3f3f3f3f, sf;

class InParser {
	char buffer[BUFF_MAX];
	int buffsize;
	char next() {
		if(buffsize == BUFF_MAX) {
			fread(buffer, 1, BUFF_MAX, stdin);
			buffsize = 0;
		}
		return buffer[buffsize++];
	}
public:
	InParser() {
		fread(buffer, 1, BUFF_MAX, stdin);
		buffsize = 0;
	}

	InParser& operator>>(int &x) {
		x = 0;
		int sgn = 1;
		char c = next();

		while((c < '0' || c > '9') && c != '-') c = next();

		if(c == '-') sgn = -1, c = next();

		while(c >= '0' && c <= '9') {
			x = x * 10 + c - '0';
			c = next();
		}

		x *= sgn;

		return *this;
	}
};

void citire() {
	InParser in;
	in >> n >> k;
	for(int i = 1; i <= n; i++)
		in >> a[i];
}

void rezolvare() {
	deq.push_back(1);

	for(int i = 2; i < k; i++) {
		while(!deq.empty() && a[i] < a[deq.back()])
			deq.pop_back();

		deq.push_back(i);
	}

	for(int i = k; i <= n; i++) {
		while(!deq.empty() && deq.front() <= i - k) 
			deq.pop_front();

		while(!deq.empty() && a[i] < a[deq.back()])
			deq.pop_back();

		deq.push_back(i);

		if(a[deq.front()] > baza_max) {
			sf = i;
			baza_max = a[deq.front()];
		}
	}
}

void afisare() {
	printf("%d %d %d\n", sf - k + 1, sf, baza_max);
}

int main() {
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);

	citire();

	rezolvare();

	afisare();

	return 0;
}