Cod sursa(job #956408)

Utilizator OpportunityVlad Negura Opportunity Data 3 iunie 2013 02:43:54
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <iostream>
#include <deque>
using namespace std;
ifstream fi("secventa.in");
ofstream fo("secventa.out");

int n,i,ind,k,a[500001],start,finis,rs=-1<<20;
string s;
deque< int > q;

int next()
{
	int semn=1,nr=0;
	if (s[ind]=='-') semn=-1,ind++;
	while (s[ind]!=' ') nr=nr*10+s[ind]-'0',ind++;
	ind++;
	return semn*nr;
}

int main()
{
	
	
	fi >> n >>k; fi.get();
	getline(fi,s); s+=' ';
	for (i=1; i<=n; i++) a[i]=next();
	//for (i=1; i<=n; i++) cout << a[i] << ' '; cout << endl;
	for (i=1; i<=n; i++)
	{
		while (!q.empty() && a[q.back()]>=a[i]) q.pop_back();
		while (!q.empty() && i-k>=q.front()) q.pop_front();
		q.push_back(i);
		if (i>=k && a[q.front()]>rs)
		{
			start=i-k+1;
			finis=i;
			rs=a[q.front()];
		}
	}
	
	fo << start << ' ' << finis << ' ' << rs;
	
	return 0;
}