Cod sursa(job #24537)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 2 martie 2007 20:02:27
Problema Lupul Urias si Rau Scor 52
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.15 kb
/*# include <stdio.h>

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

# define  maxn  1000//02


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


void readf()
{
	freopen(_fin, "r", stdin);
	int i;
	
	for (scanf("%d%d%d", &n, &x, &dl), i=1; i<=n; i++)
		 scanf("%d%d", d+i, l+i), t[i] = d[i] + (x-d[i])/dl * 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 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=1;
	
	for (j=t[n]; j>=1; 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();
}
*/

# include <stdio.h>

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

# define maxn 100010


int n, v[maxn][2], l, x;
int p[maxn][2]; // pozitiile de inceput / sfarsit pentru intervale
long long sol;


void readf()
{
    int i, d, vl;
    FILE *fin = fopen(_fin, "r");
    
# define interval(a) ( (a+l-1) / (l) )
    
    for(fscanf(fin, "%d %d %d", &n, &x, &l), i=1; i<=n; i++)
        fscanf(fin, "%d %d", &d, &vl),
        v[i][0] = interval(d), v[i][1] = vl;

# undef interval
        
    fclose(fin);
}

int qs_poz(int st, int dr)
{
    int xi = v[st][0], xd = v[st][1];
    
    while ( st < dr )
    {
        while ( st < dr && ( v[dr][0] > xi || ( v[dr][0] == xi && v[dr][1] >= xd ) ) ) dr--;
        v[st][0] = v[dr][0], v[st][1] = v[dr][1];
        while ( st < dr && ( v[st][0] < xi || ( v[st][0] == xi && v[st][1] <= xd ) ) ) st++;
        v[dr][0] = v[st][0], v[dr][1] = v[st][1];
    }
    
    v[st][0] = xi, v[st][1] = xd;
    
    return st;
}

void qs_normal(int st, int dr)
{
    int m = qs_poz(st, dr);
    if ( st < m ) qs_normal(st, m-1);
    if ( m < dr ) qs_normal(m+1, dr);
}

void solve()
{
    qs_normal(1, n);
    
    int i, j, st, max, maxi = -1;
    
    for(i=1; i<=n; i++)
    {
        if ( !p[ v[i][0] ][0] ) p[ v[i][0] ][0] = i;
        p[ v[i][0] ][1] = i;        // ultima aparitie
        
        if ( v[i][0] > maxi ) maxi = v[i][0];
    }
    
    // intervalul X se afla pe pozitiile p[ X ][ 0 ] ...  p[ X ][ 1 ]
    for(st=0; ! p[st][0]; st++);
    
    // ne aflam pe primul interval
    sol += (long long)v[ p[st][1]-- ][1]; // adaugam maximul din interval
    
    for(i=st+1; i<=maxi; i++)
    {
        // care e maximul dintre ce a ramas si ce mai este
        max = i;
        
        for(j=i; j>=st; --j)
        {
            if ( p[j][1] < p[j][0] ) // nu avem interval
                continue;
                
            if ( v[ p[j][1] ][1] > v[ p[max][1] ][1] )
                max = j;
            // daca avem un numar mai mare
        }
        
        // adunam valoarea gasita la max
        sol += (long long)v[ p[max][1] ][ 1 ];
        p[ max ][ 1 ]--; // scoatem acea valoarea din interval
    }
}

void writef()
{
    FILE *fout = fopen(_fout, "w");
    fprintf(fout, "%lld\n", sol), fclose(fout);
}

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