Pagini recente » Cod sursa (job #612576) | Cod sursa (job #3264935) | Cod sursa (job #3142623) | Cod sursa (job #239459) | Cod sursa (job #223308)
Cod sursa(job #223308)
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX_N 100005
#define DIM 8192
int N, logN;
long A[MAX_N], B[MAX_N], Bst[MAX_N];
int P[MAX_N];
int Max;
char buf[DIM];
int pz;
void read(long &x)
{
x = 0;
while(!isdigit(buf[pz]))
if(++pz == DIM)
fread(buf, sizeof buf, DIM, stdin), pz = 0;
while(isdigit(buf[pz]))
{
x = x*10 + (buf[pz] - '0');
if(++pz == DIM)
fread(buf, sizeof buf, DIM, stdin), pz = 0;
}
}
void citire()
{
long n;
read(n);
N = (int) n;
for(int i = 1; i <= N; ++i)
{
read(A[i]); read(B[i]);
P[i] = i;
}
}
struct cmp
{
bool operator()(const int a, const int b) const
{
return (B[a] < B[b]);
}
};
int b_search(int x)
{
int i, lg;
for(i = 0, lg = logN; lg; lg >>= 1)
if(i + lg <= N && B[P[i + lg]] <= x)
i += lg;
return i;
}
void solve()
{
sort(P+1, P+N+1, cmp());
/* for(logN = 1; logN <= N; logN <<= 1);
for(int i = 1; i <= N; ++i)
{
Bst[i] = Bst[i-1];
int poz = b_search(A[P[i]]);
int dif = B[P[i]] - A[P[i]];
if(dif + Bst[poz] > Bst[i])
Bst[i] = dif + Bst[poz];
if(Bst[i] > Max)
Max = Bst[i];
}
printf("%d\n",Max); */
}
int main()
{
freopen("heavymetal.in","rt",stdin);
freopen("heavymetal.out","wt",stdout);
citire();
solve();
}