Cod sursa(job #2979485)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 15 februarie 2023 10:59:26
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("popcnt")

using namespace std;

ifstream fin  ("heavymetal.in");
ofstream fout ("heavymetal.out");

const int MAX_N = 100'000;
int n;
struct concert{
    int a, b, l;
    inline bool operator < (const concert &rhs) const{
        if(b != rhs.b)
            return b < rhs.b;
        return a > rhs.a;
    }
} c[MAX_N + 5];

int bcnt, bounds[2 * MAX_N + 5];
map <int, int> normal;

int m;
struct SEGTREE{
    int aint[4 * MAX_N + 5];

    inline void build(int nod=1, int st=1, int dr=m){
        if(st == dr){
            aint[nod] = 0;
        }else{
            int md = ((st + dr) >> 1);
            build(2*nod  , st  , md);
            build(2*nod+1, md+1, dr);
            aint[nod] = max(aint[2*nod], aint[2*nod+1]);
        }
    }

    inline int query(int qst, int qdr, int nod=1, int st=1, int dr=m){
        if(qst <= st && dr <= qdr){
            return aint[nod];
        }else{
            int md = ((st + dr) >> 1), answer = 0;
            if(qst <= md) answer = max(answer, query(qst, qdr, 2*nod  , st  , md));
            if(qdr >  md) answer = max(answer, query(qst, qdr, 2*nod+1, md+1, dr));
            return answer;
        }
    }

    inline void update(int poz, int val, int nod=1, int st=1, int dr=m){
        if(st == dr){
            aint[nod] = val;
        }else{
            int md = ((st + dr) >> 1);
            if(poz <= md)
                update(poz, val, 2*nod  , st  , md);
            else
                update(poz, val, 2*nod+1, md+1, dr);
            aint[nod] = max(aint[2*nod], aint[2*nod+1]);
        }
    }
} tree;

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>n;
    for(int i=1; i<=n; i++){
        fin>>c[i].a>>c[i].b;
        c[i].l = c[i].b - c[i].a;
        bounds[++bcnt] = c[i].a;
        bounds[++bcnt] = c[i].b;
    }

    sort(bounds+1, bounds+bcnt+1);
    for(int i=1, cnt=0; i<=bcnt; i++)
        if(bounds[i-1] != bounds[i])
            normal[bounds[i]] = ++cnt;

    for(int i=1; i<=n; i++){
        c[i].a = normal[c[i].a];
        c[i].b = normal[c[i].b];
    }
    sort(c+1, c+n+1);

    m = c[n].b;
    tree.build();
    for(int i=1, newval; i<=n; i++){
        newval = tree.query(1, c[i].a) + c[i].l;
        if(newval > tree.query(c[i].b, c[i].b))
            tree.update(c[i].b, newval);
    }
    fout<<tree.query(1, m);
    return 0;
}
/**

**/