Cod sursa(job #385539)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 22 ianuarie 2010 21:52:48
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<utility>
#include<deque>
using namespace std;
deque<pair<int,int> > Q;
int n,k,val,ps,us,bs,i;
char data[3500000],*c;
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	fgets(data,3500000,stdin);
	c=data;
	n=atoi(c);c=strchr(c,' ');c++;
	k=atoi(c);c=strchr(c,' ');c++;
	fgets(data,3500000,stdin);
	c=data;	
}
void solve()
{
	for(i=1;i<k;i++)
	{
		val=atoi(c);c=strchr(c,' ');c++;
		while(!Q.empty()&&Q.back().first>val)Q.pop_back();
		Q.push_back(make_pair(val,i));
	}
	bs=-30010;
	for(i=k;i<=n;i++)
	{
		val=atoi(c);c=strchr(c,' ');c++;
		while(!Q.empty()&&Q.back().first>val)Q.pop_back();
		Q.push_back(make_pair(val,i));
		if(Q.front().second==i-k)Q.pop_front();
		if(Q.front().first>bs){bs=Q.front().first;us=i;}
	}
	ps=us-k+1;
	printf("%d %d %d\n",ps,us,bs);
}