Pagini recente » Cod sursa (job #1642067) | Cod sursa (job #250434) | Cod sursa (job #1893307) | Cod sursa (job #2513711) | Cod sursa (job #2970454)
#include <fstream>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#define ll long long
using namespace std;
const int NMAX = 100000;
struct ob
{
int a, b;
int dif;
} v[NMAX + 1];
bool cmp(ob a, ob b)
{
return a.dif > b.dif;
}
int cnt;
int aib[NMAX + 1];
map <int, int> mp;
int query(int val)
{
int ans = 0;
for (;val; val -= val & -val)
ans += aib[val];
return ans;
}
void update(int poz, int val)
{
for (; poz <= cnt; poz += poz & -poz)
aib[poz] += val;
}
int main()
{
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
int n, i;
cin >> n;
for (i = 1; i <= n; i++)
{
cin >> v[i].a >> v[i].b;
v[i].dif = v[i].b - v[i].a;
mp[v[i].a] = 0;
mp[v[i].b] = 0;
}
sort(v + 1, v + n + 1, cmp);
for (auto it = mp.begin(); it != mp.end(); it++)
it->second = ++cnt;
long long ans = 0;
for (i = 1; i <= n; i++)
if (query(mp[v[i].b] - 1) - query(mp[v[i].a] - 1) == 0)
{
ans += v[i].dif;
update(mp[v[i].a], 1);
update(mp[v[i].b], -1);
}
cout << ans;
}