Cod sursa(job #167932)

Utilizator tm_raduToma Radu tm_radu Data 30 martie 2008 13:39:50
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <stdio.h>
#define NM 100001
#define lf (nod<<1)
#define rt (lf+1)
#define Max(a, b) ((a) > (b) ? (a) : (b))

int n, tmax;
int t[NM];
int i, j, k;
int a[NM], b[NM];
int max[3*NM];
int maxim, pos;

void Qsort(int st, int dr);
void Cbin(int st, int dt);
void Update(int nod, int st, int dr, int pos);
void Query(int nod, int st, int dt, int a, int b);

int main()
{
	freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);
    scanf("%d", &n);
    for ( i = 1; i <= n; i++ )
        scanf("%d %d", &a[i], &b[i]);
    Qsort(1, n);
    for ( i = 1; i <= n; i++ )
    {
        t[i] = t[i-1]; 
		Cbin(0, i-1);
		maxim = 0;
		Query(1, 0, n, 0, pos);
		t[i] = maxim + b[i]-a[i];
        Update(1, 0, n, i);
        if ( t[i] > tmax ) tmax = t[i];
    }        
    
    printf("%d\n", tmax);
    
    return 0;
}

void Qsort(int st, int dr)
{
    int i = st-1;
    int j = dr+1;
    do
    {
        do { i++; } while ( b[i] < b[st] || (b[i] == b[st] && a[i] > a[st]) );
        do { j--; } while ( b[st] < b[j] || (b[st] == b[j] && a[st] > a[j]) );
        if ( i <= j )
        {
            int aux = a[i]; a[i] = a[j]; a[j] = aux;
            aux = b[i]; b[i] = b[j]; b[j] = aux;
        }
    } while ( i <= j );
    if ( i < dr ) Qsort(i, dr);
    if ( st < j ) Qsort(st, j);
}

void Cbin(int st, int dr)
{
    while ( st != dr )
    {
        int mij = (st+dr)/2+1;
        if ( b[mij] <= a[i] ) st = mij;
        else                  dr = mij-1;
    }
    pos = st;
}

void Query(int nod, int st, int dr, int a, int b)
{
    if ( a <= st && dr <= b )
    {
        maxim = maxim < max[nod] ? max[nod] : maxim;
        return;
    }
    int mij = (st+dr)/2;
    if ( a <= mij ) Query(lf, st, mij, a, b);
    if ( mij < b ) Query(rt, mij+1, dr, a, b);
}

void Update(int nod, int st, int dr, int pos)
{
    if ( st == dr )
    {
        max[nod] = t[pos];
        return;
    }
    int mij = (st+dr)/2;
    if ( pos <= mij ) Update(lf, st, mij, pos);
    if ( mij < pos ) Update(rt, mij+1, dr, pos);
    max[nod] = max[lf] > max[rt] ? max[lf] : max[rt];
}