Cod sursa(job #480908)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 30 august 2010 02:45:14
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<fstream>
#include<iostream>
#include<deque>

using namespace std;

int main()
{
	int N,K;
	long x,max=-30001;
	fstream fin("secventa.in", fstream::in);
	fstream fout("secventa.out", fstream::out);
	deque<pair<long,long> > deq;
	pair<long, long> pr;
	
	fin>>N>>K;
	//cout<<N<<" "<<K<<endl;
	for(int i=1; i<=N; ++i)
	{
		fin>>x;
		while(!deq.empty() && deq.back().second>=x)
			deq.pop_back();
		deq.push_back(make_pair(i,x));
		//cout<<"pos "<<deq.back().first<<" "<<i-K<<endl;
		while(!deq.empty() && deq.front().first<=i-K)
		{
			//cout<<"doing"<<endl;
			deq.pop_front();
		}
		if(deq.front().second>max && i>=K)
		{
			max=deq.front().second;
			pr=make_pair(i,deq.front().second);
			//cout<<max<<" ";
		}
	}
	fout<<pr.first-K+1<<" "<<pr.first<<" "<<pr.second<<endl;
	
	fin.close();
	fout.close();
	return 0;
}