Cod sursa(job #2970454)

Utilizator AswVwsACamburu Luca AswVwsA Data 25 ianuarie 2023 10:36:40
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#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;
}