Cod sursa(job #24542)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 2 martie 2007 20:18:20
Problema Lupul Urias si Rau Scor 72
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
# include <stdio.h>
# include <stdlib.h>

# define  _fin  "lupu.in"
# define  _fout "lupu.out"

# define  maxn  100002


int n, x, dl, l[maxn], t[maxn];
int a[maxn];
long long sol;


void readf()
{
	FILE *fin = fopen(_fin, "r");
//	freopen(_fin, "r", stdin);
	int i, d;
	char buf[24];
	
	for (fscanf(fin, "%d%d%d\n", &n, &x, &dl), i=1; i<=n; i++)
	{
		fgets(buf, 23, fin);
		sscanf(buf, "%d%d", &d, l+i), t[i] = (x-d) / dl;
	}
}

// HEAP
inline int st(int x) { return x<<1; }
inline int dr(int x) { return (x<<1)|1; }
inline int pr(int x) { return x>>1; }

void reheap(int i)
{
	int max;
	
	while ( 1 )
	{
		max = i;
		if ( st(i) <= a[0] && a[st(i)] >= a[max] ) max = st(i);
		if ( dr(i) <= a[0] && a[dr(i)] >= a[max] ) max = dr(i);
		
		if ( max==i ) break;
		
		a[i] ^= a[max] ^= a[i] ^= a[max];
		i=max;
	}
}

void insert(int x)
{
	int pos=++a[0];
	while ( a[ pr(pos) ] < x && pos > 1 )
		a[ pos ] = a[ pr(pos) ], pos = pr(pos);
	a[pos] = x;
}

int getmax()
{
	if ( !a[0] ) return 0;

	int ret = a[1];
	a[1] = a[ a[0]-- ];
	reheap(1);
	
	return ret;
}

// qs -> sort t + l
int qspoz(int st, int dr)
{
	int x=t[st], xl=l[st];
	
	while ( st < dr )
	{
		while ( st < dr && t[dr] >= x ) dr--;
		t[st] = t[dr], l[st] = l[dr];
		while ( st < dr && t[st] <= x ) st++;
		t[dr] = t[st], l[dr] = l[st];
	}
	t[st] = x, l[st] = xl;
	return st;
}

void qs(int st, int dr)
{
	int p = rand() % (dr-st+1)+st;
	if ( p!=st )
		t[p] ^= t[st] ^= t[p] ^= t[st], l[p] ^= l[st] ^= l[p] ^= l[st];

	int m = qspoz(st, dr);
	if ( st < m ) qs(st, m-1);
	if ( m < dr ) qs(m+1, dr);
}

void solve()
{
	qs(1, n);
	int j, crt=n;
	
	for (j=t[n]; j>=0; j--)
	{
		// inseram cele cu ti = j
		while ( t[crt]>=j && crt>=1 )
			insert( l[crt--] );

		sol += (long long)getmax();
	}
}

void writef()
{
	freopen(_fout, "w", stdout);
	printf("%lld\n", sol);
}

int main()
{
	readf();
	solve();
	writef();
}