Cod sursa(job #138216)

Utilizator cos_minBondane Cosmin cos_min Data 17 februarie 2008 23:03:24
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <stdio.h>
#include <algorithm>
#include <fstream>
#include <set>
#include <utility>
using namespace std;

#define in "heavymetal.in"
#define out "heavymetal.out"
#define dim 100001

inline int Maxim(int a, int b) {
       if ( a > b ) return a;
       return b;
}

int N, maxim;
int Poz, Val, st, dr, middle;
int S[dim], F[dim], C[dim], A[dim];
int Arb[2*dim+66];

set< pair<int,int> > H;
set< pair<int,int> >::iterator it, it2;

void Update(int,int,int);
void Query(int,int,int);

int main()
{
    int X, Y;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d", &N);
    for ( int i = 1; i <= N; i++ )
    {
        scanf("%d%d", &X, &Y);
        H.insert( make_pair(X,Y) );
    }
    
    int k = 1;
    for ( it = H.begin(); it != H.end(); it++, k++ )
        C[k] = it->second - it->first, S[k] = it->first, F[k] = it->second;
    
    memset(A,0,sizeof(A));
    
    maxim = 0;
    Val = C[1], Poz = 1;
    A[1] = C[1];
    
    Update(1,1,N);
    
    int T = A[1];
    
    for ( int i = 2; i <= N; i++ )
    {
        int k, j;
        
        for ( j = i-1; j >= 1; j-- )
            if ( F[j] <= S[i] ) break;
        
        for ( k = 1; k <= j; k++ )
            if ( F[k] <= S[i] ) break;
        
        if ( j == 0 || k > j ) 
        {
             A[i] = C[i], Val = C[i], Poz = i;
             Update(1,1,N);
             
             if ( T < A[i] ) T = A[i]; 
             continue;
        }
        
        if ( j == 1 && S[i] < F[j] ) 
        {
             A[i] = C[i], Val = C[i], Poz = i;
             Update(1,1,N);
             
             if ( T < A[i] ) T = A[i]; 
        }
        else 
        {
             maxim = 0, st = k, dr = j;
             Query(1,1,N);
             
             A[i] = maxim + C[i]; 
             
             Val = A[i], Poz = i;
             Update(1,1,N);
             
             if ( T < A[i] ) T = A[i];  
        } 
    }
    
    printf("%d", T);
}

void Update(int nod, int left, int right)
{
     if ( left == right )
     {
          Arb[nod] = Val;
          return;
     }
     
     middle = (left+right)>>1;
     if ( Poz <= middle ) Update(2*nod,left,middle);
     else                 Update(2*nod+1,middle+1,right);
     
     Arb[nod] = Maxim( Arb[2*nod], Arb[2*nod+1] );
}

void Query(int nod, int left, int right)
{
     if ( st <= left && right <= dr )
     {
          maxim = Maxim(maxim,Arb[nod]);
          return;
     }
     
     middle = (left+right)>>1;
     if ( st <= middle ) Query(2*nod,left,middle);
     if ( middle < dr )  Query(2*nod+1,middle+1,right);
}