Pagini recente » Cod sursa (job #722813) | Cod sursa (job #462275) | Cod sursa (job #1054109) | Cod sursa (job #1128835) | Cod sursa (job #1876819)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 666013
#define N 100000
#define INF 0x3f3f3f3f
#define iter vector<pair<int, int> >::iterator
using namespace std;
class hash_table {
vector<pair<int, int> > L[MOD];
public: int &operator[](int x) {
int v = x % MOD;
iter it;
for (it = L[v].begin(); it != L[v].end() && it -> first != v; ++it);
if (it == L[v].end()) {
L[v].push_back(make_pair(x, -INF));
return L[v][L[v].size() - 1].second;
}
return it -> second;
}
};
hash_table H;
int A[N], B[N], I[N];
bool comp(int a, int b) {
return B[a] < B[b];
}
int main() {
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n;
fin >> n;
for (int i = 0; i < n; ++i) {
int a, b;
fin >> a >> b;
A[i] = a;
B[i] = b;
I[i] = i;
}
sort(I, I + n, comp);
H[B[I[0]]] = B[I[0]] - A[I[0]];
for (int i = 1; i < n; ++i) {
// Binary-search for the event ending with A[i]
int step, val;
for (step = 1; step < i; step <<= 1);
for (val = 0; step; step >>= 1) {
int v = val + step;
if (v < i && B[I[v]] <= A[I[i]])
val = v;
}
if (B[I[val]] <= A[I[i]])
H[B[I[i]]] = max(H[B[I[i]]], H[B[I[val]]] + B[I[i]] - A[I[i]]);
else
H[B[I[i]]] = B[I[i]] - A[I[i]];
}
fout << H[B[I[n - 1]]] << "\n";
return 0;
}