Cod sursa(job #196285)

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

using namespace std;

int T_MAX,N,X,L;
int T[N_MAX],nr[N_MAX],H[N_MAX];
vector< vector<int> > A(N_MAX);     
long long suma;

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,y;
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d%d%d", &N,&X,&L);
	FOR(i,1,N) 
	{
		scanf("%d%d",&x,&y);
		T[i]=(X-x)/L;
		++nr[T[i]];
		//printf("%d ", T[i]);
		if(T[i]>=0)
			A[T[i]].pb(y);   

		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(int i=T_MAX;i>=0;--i)
	{
		FOR(j,0,nr[i]-1)
			insert(++last,A[i][j]);
		if(last)
		{
			suma+=H[1];
			cut(last,1);
			--last;
		}	
	}
	printf("%lld\n",suma);
}

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