Cod sursa(job #47807)

Utilizator gigi_becaliGigi Becali gigi_becali Data 3 aprilie 2007 23:54:21
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <cstdio>
#include <map>
#include <string>
#include <cstdlib>
#define maxn 1<<19
#define left(i) ((i)<<1)
#define right(i) (((i)<<1)|1)
#define tata(i) ((i)>>1)
using namespace std;

int x[maxn];
int n, m;
char ax[10000000];
void citire()
{
	freopen("secventa.in", "r", stdin);
	scanf("%d %d\n", &n, &m);
	
	gets(ax);
	
	char *p;
	p=strtok(ax, " \n");
	x[1]=atoi(p);
//	p=strtok(0, " \n");
//	m=atoi(p);
	
	//x[2]=atoi(p);
	int i;
	for(i=2;i<=n;i++) 
	{
		p=strtok(0, " \n");
		x[i]=atoi(p);
	}
	
		//scanf("%d ", &x[i]);
}
int H[maxn], poz[maxn],nh;
void swap(int i, int j)
{
	int t=H[i];H[i]=H[j];H[j]=t;
	poz[j]=i;
	poz[i]=j;
}


void upheap(int i)
{
	if(i==1) return ;
	if(H[i]<H[tata(i)]) swap(i, tata(i)), upheap(tata(i));
}

void downheap(int i)
{
	int min=i;
	if(left(i)<=nh && H[i]>H[left(i)]) min=left(i);
	if(right(i)<=nh && H[min]>H[right(i)]) min=right(i);
	if(i!=min) swap(i, min), downheap(min);
}

inline void insert(int val)
{
	H[++nh]=val;
	upheap(nh);
}


void solve()
{
	int i, j;
	map<int, int> Q;
	int max=-1000000, pi=0, pf=m;
	//for(i=1;i<=n;i++) printf("%d ", x[i]);
	//printf("\n");
//for(i=1;i<m;i++) poz[i]=i;
	for(i=1;i<m;i++) insert(x[i]);

	
	
	for(i=m;i<=n;i++)
	{
		//poz[i]=i;
		insert(x[i]);
	
		int min=H[1];
		if(min>max) max=min, pi=i-m+1, pf=i;
		swap(nh, poz[i-m+1]);
		nh--;
		downheap(poz[i-m+1]);
		
		
	}
	freopen("secventa.out", "w", stdout);
	printf("%d %d %d\n", pi, pf, max);
}


int main()
{
	citire();
	solve();
return 0;
}