Pagini recente » Cod sursa (job #754919) | Cod sursa (job #3278906) | Cod sursa (job #371132) | Cod sursa (job #2094361) | Cod sursa (job #137939)
Cod sursa(job #137939)
#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;
}