Cod sursa(job #137935)

Utilizator cos_minBondane Cosmin cos_min Data 17 februarie 2008 17:31:56
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 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

int N;
int X[dim], Y[dim], C[dim], P[dim];

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

bool compare(int i, int j)
{
     return C[i] > C[j];
}

int BinaryS(int,int);

int main()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d", &N);
    for ( int i = 1; i <= N; i++ )
        scanf("%d%d", &X[i], &Y[i]), C[i] = Y[i]-X[i], P[i] = i;
    
    sort( P+1, P+N+1, compare );
    
    int T = 0;
    
    for ( int i = 1; i <= N; i++ )
    {
        //printf("%d %d\n", X[P[i]], Y[P[i]] );
        if ( BinaryS(X[P[i]],Y[P[i]]) ) 
        {
             T += C[P[i]], H.insert( make_pair(X[P[i]],Y[P[i]]) );
             
        }
    }
    
    printf("%d", T);
}

int BinaryS(int val, int val2)
{
    if ( H.size() == 0 ) return 1;
    
    it = H.upper_bound( make_pair(val,val2) );
    it2 = H.lower_bound( make_pair(val,val2) );
    
  //  printf("%d %d: %d %d | %d %d\n", val, val2, it->first, it->second, it2->first, it2->second );
    
    if ( it->first < val && val <= it->second ) return 0;
    if ( it2->first < val && val <= it2->second ) return 0;
    if ( it->first < val2 && val2 <= it->second ) return 0;
    if ( it2->first < val2 && val2 <= it2->second ) return 0;
    
    return 1;
}