Cod sursa(job #770475)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 23 iulie 2012 10:52:27
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<fstream>
#include<deque>

using namespace std;

deque < pair <int, int> > A;

int n, k, x, y, res = -30001;

int main()
{
	ifstream f("secventa.in");
	
	int i, val;
	
	f >> n >> k;
	for(i = 1; i < k; i++)
	{
		f >> val;
		
		while(!A.empty() && val <= A.back().second)
			A.pop_back();
		A.push_back(make_pair(i, val));
		
		if(i - k == A.front().first)
			A.pop_front();
	}
	
	for( ; i <= n; i++)			
	{
		f >> val;
		
		while(!A.empty() && val <= A.back().second)
			A.pop_back();
		A.push_back(make_pair(i, val));
		
		if(i - k == A.front().first)
			A.pop_front();
		
		if(A.front().second > res)
			res = A.front().second, y = i;
	}
	
	f.close();
	
	x = y - k + 1;
	
	ofstream g("secventa.out");
	
	g << x << " " << y << " " << res << '\n'; 
	
	g.close();

	return 0;
}