Cod sursa(job #867512)

Utilizator superman_01Avramescu Cristian superman_01 Data 29 ianuarie 2013 19:41:02
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<fstream>
#include<cstdio>
#include<deque>
#define NMax 5000005

using namespace std;
FILE *f=fopen("secventa.in","r");
ofstream g("secventa.out");
 
deque <int> Q;
char q[NMax];
int v[NMax];
long long s,smax;
int n,k,start,finish,cont,cont_copy;
void read()
{
     
    int i,j;
    fscanf(f,"%d%d",&n,&k);
	fgets(q,5000005,f);
	fgets(q,5000005,f);
	int nr=0,sign=0;
	for(i=0;q[i];i++)
	{
		if(q[i]>='0'&&q[i]<='9')
			nr=nr*10+q[i]-'0';
		else
			if(q[i]=='-')
				sign=1;
			else
				if(q[i]==' ')
				{
					if(sign==1)
						nr*=-1;
					   sign=0;
						v[++v[0]]=nr;
						nr=0;
				}
	}
		if(sign==1)
						nr*=-1;
					   sign=0;
						v[++v[0]]=nr;
						nr=0;
     
}
void solve()
{
    int i,j,cont;
	cont=-200000;
    for(i=1;i<=v[0];i++)
    {
        while(Q.size()&&v[Q.back()]>=v[i])
        Q.pop_back();
         
        Q.push_back(i);
     
        if(Q.front()==(i-k) )
             Q.pop_front();
		
        if(i>=k)
        {  
			
          if(v[Q.front()]>cont)
		  {
			 
			  start=i-k+1;
			  finish=i;
			  cont=v[Q.front()];
			  
		  }		
		}		  
    }
     cont_copy=cont;
}
void write()
{
    g<<start<<" "<<finish<<" "<<cont_copy;
}
 
int main()
{
    int i,j;
    read();
    solve();
    write();
    return 0;
}