Cod sursa(job #973793)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 15 iulie 2013 15:50:39
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>

using namespace std;

char sir[4000050];
int q[500010],ind[500010];

inline int Creeaza(int &indice)
{
	int sign,x;
	if(sir[indice]=='-')
	{
		sign=-1;
		indice++;
	}
	else
		sign=1;
	x=0;
	while(sir[indice]>='0' && sir[indice]<='9')
	{
		x=x*10+sir[indice]-'0';
		indice++;
	}
	indice++;
	return x*sign;
}

int main()
{
	int n,k,i,pr,ul,x,max,poz,p,indice;
	ifstream fin("secventa.in");
	ofstream fout("secventa.out");
	fin>>n>>k;
	fin.get();
	fin.getline(sir,3500000);
	pr=0;ul=-1;indice=0;
	for (i=1;i<=k;i++)
	{
	   //scanf("%d",&x) ;
		x=Creeaza(indice);
	   while ((pr<=ul)&&(q[ul] >= x)) ul-- ;
	   q[++ul] = x ;
	   ind[ul] = i ;
	}
	max = q[pr] ;
	poz = 1 ;
	p = 1;
	// calculez restul:
	for ( ; i<=n; i++)
	{
	   //scanf("%d",&x) ;
		x=Creeaza(indice);
	   while ((q[ul] >= x) && (pr<=ul)) ul-- ;
	   q[++ul] = x ;
	   ind[ul] = i ;
	   p++ ;
	   if (ind[pr] <= i-k) pr++ ;
	   if (max < q[pr]) { max = q[pr] ;poz = p; }
	}
	fout<<poz<<" "<<poz+k-1<<" "<<max;
	fin.close();
	fout.close();
	return 0;
}