Cod sursa(job #745238)

Utilizator gabrielvGabriel Vanca gabrielv Data 10 mai 2012 20:10:36
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 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;
long long S;
vector < pair < int , int > > 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--;
	sift(n,i); // pentru ca nu vom elimina decat elementul maxim, nu va fi necesar percolade()
}
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);
	}
}
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("%lld\n",S);
}
int main()
{
	go(0,0,oaie);
	citire();
	BVO();
	afisare();
	return 0;
}