Cod sursa(job #972214)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 11 iulie 2013 11:55:42
Problema Secventa Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int st[500001],poz[500001];

int main()
{
	int n,k,i,top,begin,x,baza,stg,drp;
	freopen ("secventa.in","r",stdin);
	freopen ("secventa.out","w",stdout);
	scanf("%d%d", &n,&k);
	top=0;stg=1;drp=k;
	for(i=1;i<=k;i++)
	{
		scanf("%d", &x);
		while(top>0 && st[top]>x)
			top--;
		st[++top]=x;
		poz[top]=i;
	}
	begin=1;
	/*for(i=1;i<=top;i++)
		printf("%d ", st[i]);
	printf("\n");*/
	baza=st[begin];
	for(i=k+1;i<=n;i++)
	{
		scanf("%d", &x);
		while(top>0 && st[top]>x)
			top--;
		st[++top]=x;
		poz[top]=i;
		while(poz[begin]<=(i-k))
			begin++;
		if(baza<st[begin])
		{
			baza=st[begin];
			drp=i;
			stg=i-k+1;
		}
	}
	printf("%d %d %d\n", stg,drp,baza);
	return 0;
}