Cod sursa(job #3121371)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 12 aprilie 2023 11:50:17
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");

const int MAX = 1e5 + 1;

int dp[MAX] , aint[4*MAX] , n;

struct interval{

    int st , dr;

}v[MAX];

bool cmp( interval a , interval b ){

    if(a.dr == b.dr) return a.st < b.st;

    return a.dr < b.dr;
}

int bs( int dr , int maxx ){

    int st = 1 , mij , ans = -1;

    while(st <= dr){

        mij = (st+dr)/2;

        if(v[mij].dr <= maxx){

            ans = mij;

            st = mij + 1;

        }else dr = mij - 1;
    }

    return ans;
}

void update( int nod , int st , int dr , int poz ){

    if(st == dr){

        aint[nod] = dp[poz];

    }else{

        int mij = (st+dr)/2;

        if(poz <= mij){

            update(nod*2,st,mij,poz);

        }else update(nod*2+1,mij+1,dr,poz);

        aint[nod] = max(aint[nod*2],aint[nod*2+1]);
    }

}

int qry( int nod , int st , int dr , int qst , int qdr ){

    if(qst <= st && dr <= qdr){

        return aint[nod];

    }else{

        int val = 0;

        int mij = (st+dr)/2;

        if(qst <= mij) val = max(val,qry(nod*2,st,mij,qst,qdr));
        if(qdr > mij) val = max(val,qry(nod*2+1,mij+1,dr,qst,qdr));

        return val;
    }
}

int main(){

    cin >> n;

    for(int i = 1 ; i <= n ; i++){

        cin >> v[i].st >> v[i].dr;
    }

    sort(v+1,v+1+n,cmp);

    int maxdp = 0;

    for(int i = 1 ; i <= n ; i++){

        int poz = bs(i-1,v[i].st);

        if(poz == -1){

            dp[i] = v[i].dr - v[i].st;

        }else{

            int maxim = qry(1,1,n,1,poz);

            dp[i] = maxim + v[i].dr - v[i].st;
        }

        maxdp = max(maxdp,dp[i]);

        update(1,1,n,i);
    }

    cout << maxdp;

    return 0;
}