Cod sursa(job #316288)

Utilizator pcinfoCarmen Popescu pcinfo Data 18 mai 2009 23:32:02
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <cstdio>
#include <deque>
#define DIM 8192 
#include <limits>


using namespace std;

char ax[DIM+16];
int pz;

struct nod { int p,v;
};

FILE * f,*g;
int n, k;
deque<nod> q;

inline void cit(int &x)
{
            x=0;
            while((ax[pz]<'0' || ax[pz]>'9') && (ax[pz]!='-'))
                        if(++pz==DIM)fread(ax, 1, DIM, f), pz=0;
            
            int neg=0;
            if(ax[pz]=='-')
            {
                        neg=1;
                        if(++pz==DIM)fread(ax, 1, DIM, f),pz=0;
            }
            
            while(ax[pz]>='0' && ax[pz]<='9')
            {
                        x=x*10+ax[pz]-'0';
                        if(++pz==DIM)fread(ax,1, DIM, f),pz=0;
            }
            if(neg) x=-x;
}

int main()
{
	int i,max,pmax,v1;
	nod e;
	
	f = fopen("secventa.in", "r");
	g = fopen("secventa.out", "w+");
	fscanf(f,"%d%d",&n,&k);
	
	
	max=-2147483647;

	for (i=1;i<=k;i++)
	{
		cit(e.v);
		e.p=i;
		while (!q.empty() && q.back().v>e.v)
			q.pop_back();
		q.push_back(e);
	}
	
	for (i=k+1;i<=n;i++)
	{
		if (i-q.front().p >= k)
			q.pop_front();
		
		cit(e.v); e.p=i; 
		while (!q.empty() && q.back().v>e.v)
			q.pop_back();

		q.push_back(e);
		
		v1=q.front().v;
		
		if (v1>max)
		{
			max=v1;
			pmax=i;
		}
	}
	
	fprintf(g,"%d %d %d\n",pmax-k+1,pmax,max);
	
	fclose(f);
	fclose(g);
	return 0;
}