Cod sursa(job #138304)

Utilizator cos_minBondane Cosmin cos_min Data 18 februarie 2008 10:31:06
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 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, start, finish, 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(Y,X) );
    }
    
    int k = 1;
    for ( it = H.begin(); it != H.end(); it++, k++ )
        C[k] = it->first - it->second, F[k] = it->first, S[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];
    int st, dr, mij, poz;
    
    for ( int i = 2; i <= N; i++ )
    {
        st = 1, dr = i-1;
        poz = 0;
        
        while ( st <= dr )
        {
              mij = (st+dr)>>1;
              if ( F[mij] <= S[i] ) st = mij+1, poz = mij;
              else                  dr = mij-1;
        }
        
        if ( poz <= 0 || F[poz] > S[i] )
        {
             A[i] = C[i];
             Poz = i, Val = A[i];
             Update(1,1,N);
             
             if ( T < A[i] ) T = A[i];
        }
        else
        {
            maxim = 0, start = 1, finish = poz;
            //Query(1,1,N);
            
            A[i] = C[i] + maxim;
            Poz = i, Val = A[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;
     }
     
     int 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 st, int dr)
{
     if ( start <= st && dr <= finish )
     {
          maxim = Maxim( maxim, Arb[nod] );
          return; 
     }
     
     int mij = (st+dr)>>1;
     int mij2 = mij;
     
     if ( start <= mij ) Query(2*nod,st,mij);
     if ( mij2 < finish ) Query(2*nod+1,mij2+1,dr);
      
}