Cod sursa(job #1064490)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 21 decembrie 2013 22:25:30
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<cstdio>
#include<deque>
#include<climits>
#include<utility>
#include<fstream>

using namespace std ;

#define cin F
ifstream F("secventa.in") ;

int N, posm, MAX = INT_MIN, K ;
deque <pair <int, int> > dq ;

int main() {
	int i, x ;
	freopen("secventa.in", "r", stdin) ;
	freopen("secventa.out", "w", stdout) ;
	//scanf("%d %d", &N, &K) ;
	cin >> N >> K;
	//scanf("%d", &x) ;
	cin >> x ;
	dq.push_back(make_pair(x, 1)) ;
	for (i = 2; i <= K; ++i) {
			//scanf("%d", &x) ;
			cin >> x ;
			while(!dq.empty() && x <= dq.back().first) {
				dq.pop_back() ;
			}
			dq.push_back(make_pair(x, i)) ;
	}
	MAX = dq.front().first ;
	posm = K ;
	for (i = K + 1; i <= N; ++i) {
		//printf("%d %d\n", dq.front().first, dq.front().second) ;
		if (dq.front().second == i - K) {
			dq.pop_front() ;
		}
		//scanf("%d", &x) ;
		cin >> x;
		while(!dq.empty() && x <= dq.back().first) {
			dq.pop_back() ;
		}
		dq.push_back(make_pair(x, i)) ;
		//printf("%d %d\n", dq.front().first, dq.front().second) ;
		if (dq.front().first > MAX) {
			MAX = dq.front().first ;
			posm = i ;
		}
	}
	printf("%d %d %d", posm - K + 1, posm, MAX) ;
	return 0 ;
}