Pagini recente » Cod sursa (job #3261294) | Cod sursa (job #467168) | Cod sursa (job #3226741) | Cod sursa (job #263692) | Cod sursa (job #1630309)
#include <bits/stdc++.h>
using namespace std;
struct Point
{
int x, y;
Point (int x = 0, int y = 0) : x(x), y(y) {};
bool operator < (const Point &other) const {
return x < other.x;
}
};
const int MAX_N = 100007;
int N, OG[MAX_N * 2];
Point A[MAX_N];
vector<int>coordinates;
void Read()
{
freopen("heavymetal.in", "r", stdin);
scanf("%d", &N);
for(int i = 0; i < N; ++i)
{
scanf("%d %d", &A[i].x, &A[i].y);
coordinates.push_back(A[i].x);
coordinates.push_back(A[i].y);
}
}
void Init()
{
sort(coordinates.begin(), coordinates.end());
coordinates.resize(unique(coordinates.begin(), coordinates.end()) - coordinates.begin());
for(int i = 0; i < N; ++i)
{
int p1 = lower_bound(coordinates.begin(), coordinates.end(), A[i].x) - coordinates.begin() + 1;
int p2 = lower_bound(coordinates.begin(), coordinates.end(), A[i].y) - coordinates.begin() + 1;
OG[p1] = A[i].x, OG[p2] = A[i].y;
A[i].x = p1;
A[i].y = p2;
}
}
struct fenwick
{
static const int lim = 2 * 100007;
vector<int>aib;
fenwick()
{
aib.resize(lim);
}
void update(int x, int val)
{
for(; x < lim; x += x &-x)
aib[x] = max(aib[x] , val);
}
int que(int x)
{
int res = 0;
for( ; x ; x -= x &-x)
res = max(res , aib[x]);
return res;
}
};
void Solve()
{
fenwick T;
sort(A, A + N);
int res = 0;
for(int i = 0; i < N; ++i)
{
int val = T.que(A[i].x) + OG[A[i].y] - OG[A[i].x];
res = max(res , val);
T.update(A[i].y , val);
}
freopen("heavymetal.out", "w", stdout);
printf("%d ", res);
}
int main() {
Read();
Init();
Solve();
return 0;
}