Cod sursa(job #750237)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 21 mai 2012 16:50:15
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<iostream>
#include<fstream>
#include<deque>

using namespace std;

ifstream in("secventa.in");
ofstream out("secventa.out");

int a[500010];//, q[500010];
deque <int> q;

int main()
{	
	int N, k, i, st, dr, rez, poz;
	
	in >> N >> k;
	
	for(i = 1; i <= N; ++i)
		in >> a[i];
	
	rez = -(1 << 20);
	st = 1, dr = 0;
	
	/*for(i = 1; i <= k - 1; ++i){
		while((st <= dr) && (a[i] <= a[ q[dr] ])) dr--;
		dr++;
		q[dr] = i;
	}
	
	for(i = k; i <= N; ++i){
		while((st <= dr) && (a[i] <= a[ q[dr] ])) dr--;
		dr++;
		q[dr] = i;
		
		while((st <= dr) && (q[st] < (i - k + 1))) st++;
		
		if(a[ q[st] ] > rez){
			rez = a[ q[st] ];
			poz = i;
		}
	}*/
	
	/*for(i = 1; i <= N; ++i){
		while((st <= dr) && (a[i] <= a[ q[dr] ]))
			dr--;
		q[ ++dr ] = i;
		
		if(q[st] + k == i)
			st++;
		
		if(i >= k)
			if(a[ q[st] ] > rez)
				rez = a[ q[st] ], poz = i;
	}*/
	
	for(i = 1; i <= N; ++i){
		if(q.front() == i - k)
			q.pop_front();
		
		while((!q.empty()) && (a[ q.back() ] >= a[i]))
			q.pop_back();
		
		q.push_back(i);
		
		if((i >= k) && a[ q.front() ] > rez)
			rez = a[ q.front() ], poz = i;
	}
		
	
	out << poz - k + 1 << " " << poz << " " << rez;
	
	return 0;
}