Cod sursa(job #196259)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 25 iunie 2008 00:44:49
Problema Lupul Urias si Rau Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <cstdio>
#include <algorithm>
#define N_MAX 1<<17
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define IN "lupu.in"
#define OUT "lupu.out"

using namespace std;

int suma,T_MAX,N,X,L;
int T[N_MAX],lana[N_MAX],H[N_MAX];

inline int father(int nod)    {return nod / 2;    }

inline int left_son(int nod)  {return nod * 2;    }

inline int right_son(int nod) {return nod * 2 + 1;}
 

void scan()
{
	int x;
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d%d%d", &N,&X,&L);
	FOR(i,1,N) 
	{
		scanf("%d%d",&x,&lana[i]);
		T[i]=(X-x)/L;
		if(T[i]>T_MAX)
			T_MAX=T[i];
	}	
}

void percolate(int N, int K)
{  
    int key = H[K];  
    while ((K > 1) && (key > H[father(K)])) 
	{  
        H[K] = H[father(K)];  
        K = father(K);  
    }  
    H[K] = key;  
}
  
void sift(int N, int K)
{
    int son;
    do 
	{
        son = 0;
        if (left_son(K) <= N) 
		{
            son = left_son(K);
            if (right_son(K) <= N && H[right_son(K)] > H[left_son(K)]) 
			{
                son = right_son(K);
            }
            if (H[son] <= H[K]) 
			{
                son = 0;
            }
        }

        if (son) 
		{
            swap(H[K], H[son]); 
            K = son;
        }
    } while (son);
}


void cut(int N, int K)
{  
    H[K] = H[N];  
    --N;  
    if ((K > 1) && (H[K] > H[father(K)])) 
	{  
        percolate(N, K);  
    } 
	else
	{  
        sift(N, K);  
    }  
}  
  
void insert(int N, int key)
{  
    H[N] = key;  
    percolate(N, N);  
}  
   
void solve()
{
	int last=0;
	FOR(val,0,T_MAX)
	{
		FOR(i,1,N)
		{
			if(T[i]!=T_MAX-val)
				continue;
			insert(++last,lana[i]);
		}
		if(last)
		{
			suma+=H[1];
			cut(last,1);
			--last;
		}	
	}
	printf("%d\n",suma);
}

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