Cod sursa(job #812189)

Utilizator krissu93FMI Tiugan Cristiana Elena krissu93 Data 13 noiembrie 2012 16:47:21
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<fstream>
#include<iostream>
#include<vector>

using namespace std;

ifstream in("secventa.in");
ofstream out("secventa.out");

int n,k;
int bmax=-30001;
int pf=0;
int pi=0;
int deq[500001];
int p[500001];
int v[500001];


void deque()
{	int i;
	int dr=0;
	int stg=1;
	for (i=1;i<=n;i++)
	{	in>>v[i];
		while  ( (stg<=dr) && (v[i]<=deq[dr])) 
					dr--;
		dr++;
		deq[dr]=v[i];
		p[dr]=i;
	if (i-p[stg]+1>k)
		stg++;
	if (i>=k)
	{
		if (deq[stg]>bmax)
		{
			bmax=deq[stg];
			pf=i;
			pi=pf-k+1;
		}
		else
		if (deq[stg]=bmax)
		{
			int pf2=i;
			int pi2=pf2-k+1;
			if (pi2<pi)
			{
				pi=pi2;
				pf=pf2;
			}
			else
			if ( (pi2=pi) && (pf2<pf))
					pf=pf2;
		}
	}
	}
}

int main ()
{
	in>>n>>k;
	deque();
	out<<pi<<' '<<pf<<' '<<bmax;
	return 0;
}