Cod sursa(job #316265)

Utilizator pcinfoCarmen Popescu pcinfo Data 18 mai 2009 23:01:35
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 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,x,max,pmax,v1,p1;
	nod e;
	
	f = fopen("secventa.in", "r");
	g = fopen("secventa.out", "w+");
	fscanf(f,"%d%d",&n,&k);
	
	
	cit(e.v);
	e.p=1;
	
	q.push_back(e);
	max=-2147483647;

	
	for (i=2;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)
		{
			e.p=q.back().p;
			q.pop_back();
		}
		q.push_back(e);
		
		v1=q.front().v;
		p1=q.front().p;
		
		if (v1>max)
		{
			max=v1;
			pmax=p1;
		}
	}
	
	fprintf(g,"%d %d %d\n",pmax,pmax+k-1,max);
	
	fclose(f);
	fclose(g);
	return 0;
}