Cod sursa(job #656043)

Utilizator an_drey_curentandreycurent an_drey_curent Data 3 ianuarie 2012 20:47:41
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<stdio.h>
#include<deque>
using namespace std;
int v[500001];
deque<int>c;
int main()
{
	int N,K,i,inceput_coada,sfarsit_coada,min_coada,inceput_max,sfarsit_max;
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d%d",&N,&K);
	scanf("%d",&v[1]);
	c.push_back(v[1]);
	inceput_coada=1;
	sfarsit_coada=1;
	min_coada=v[1];
	for(i=2;i<=N;i++)
	{
		scanf("%d",&v[i]);
		if(sfarsit_coada-inceput_coada+1<K)
		{
			while(v[i]<c.back())
				c.pop_back();
			c.push_back(v[i]);
			sfarsit_coada++;
		}
		else
		{
			if(v[i]>=c.front())
			{
				while(c.size()&&v[i]>=c.front()&&sfarsit_coada-inceput_coada+1>=K)
				{
					inceput_coada++;
					c.pop_front();
				}
				while(c.size()&&v[i]<c.back())
					c.pop_back();
				c.push_back(v[i]);
			    sfarsit_coada++;
				if(min_coada<c.front())
				{
					min_coada=c.front();
					inceput_max=inceput_coada;
					sfarsit_max=sfarsit_coada;
				}
			}
			else
			{
				if(min_coada<c.front())
				{
					min_coada=c.front();
					inceput_max=inceput_coada;
					sfarsit_max=sfarsit_coada;
				}
				while(c.size())
					c.pop_back();
				c.push_back(v[i]);
				inceput_coada=i;
				sfarsit_coada=i;
			}
		}
	}
	printf("%d %d %d",inceput_max,sfarsit_max,min_coada);
	return 0;
}