Cod sursa(job #745232)

Utilizator gabrielvGabriel Vanca gabrielv Data 10 mai 2012 19:57:23
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#define NMAX 100005
#define maxim(a,b) ((a>b)?(a):(b))
#define lastm(d) (((X-d)/L)+1)
#define go(x,y,v) (v.push_back(make_pair(x,y)))

using namespace std;

int H[NMAX];
int N,X,L,Tmax,n;
int S;
vector < pair < int , int > > oaie;
void citire()
{
	freopen("lupu.in","r",stdin);
	scanf("%d %d %d",&N,&X,&L);
	int i,d,l;
	for(i=1;i<=N;i++)
	{
		scanf("%d %d",&d,&l);
		go(lastm(d),l,oaie);
	}
}
inline int father(int nod)
{
    return nod>>1;
}
inline int left_son(int nod)
{
    return nod<<1;
}
inline int right_son(int nod)
{
    return (nod<<1)+1;
}
void swap(int i, int j)
{
    int aux;
    aux=H[i];
    H[i]=H[j];
    H[j]=aux;
}
void percolate(int i)
{
    while(i>1 && H[i]>H[father(i)])
    {
        swap(i,father(i));
        i=father(i);
    }
}
void sift(int n, int i)
{
    int son;
    do
    {
        son=0;
        if(left_son(i)<=n)
        {
            son=left_son(i);
            if(right_son(i)<=n && H[son]<H[right_son(i)])
                son=right_son(i);
            if(H[son]<=H[i])
                son=0;
        }
        if(son)
            swap(i,son);
        i=son;
    }while(son);
}
void insert(int i)
{
	H[++n] = i;
    percolate(n);
}
void cut(int i)
{
    swap(i,n);
    n--;
    if(i>1 && H[i]>H[father(i)])
        percolate(i);
    else
        sift(n,i);
}
void BVO()
{
	sort(oaie.begin()+1,oaie.end());
	reverse(oaie.begin()+1,oaie.end());
	int j,i;
	for(j=oaie[1].first,i=1;j;j--)
	{
		for(;oaie[i].first==j && i<= N;i++)
			insert(oaie[i].second);
		if(n)
		{
			S+=H[1];
			cut(1);
		}
	}
}
void afisare()
{
	freopen("lupu.out","w",stdout);
	printf("%d",S);
}
int main()
{
	go(0,0,oaie);
	citire();
	BVO();
	afisare();
	return 0;
}