Cod sursa(job #2979458)

Utilizator LucaMihaiLM10Luca Ilie LucaMihaiLM10 Data 15 februarie 2023 09:34:28
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <bits/stdc++.h>

using namespace std;

struct aaa {
    int s, f;

    bool operator < (const aaa &a) const {
        if ( s == a.s )
            return f < a.f;
        return s < a.s;
    }
};

const int maxN = 1e5;

aaa v[maxN];
map<int, int> valToNorm;

struct AIB {
    int n;
    int aib[maxN + 1];

    void init( int _n ) {
        for ( int i = 0; i <= n; i++ )
            aib[i] = 0;
        n = _n;
    }

    void update( int i, int x ) {
        while ( i <= n ) {
            aib[i] = max( aib[i], x );
            i += (i & -i);
        }
    }

    int query( int i ) {
        int maxx = 0;

        while ( i > 0 ) {
            maxx = max( maxx, aib[i] );
            i -= (i & -i);
        }

        return maxx;
    }
};

AIB maxTime;

int main() {
    ifstream cin( "heavymetal.in" );
    ofstream cout( "heavymetal.out" );
    int n;

    cin >> n;
    for ( int i = 0; i < n; i++ ) {
        cin >> v[i].s >> v[i].f;
        valToNorm[v[i].s] = valToNorm[v[i].f] = 1;
    }
    sort( v, v + n );

    int val = 1;
    for ( auto p: valToNorm )
        valToNorm[p.first] = ++val;

    maxTime.init( val );
    for ( int i = 0; i < n; i++ ) {
        int time = maxTime.query( valToNorm[v[i].s] );
        time += v[i].f - v[i].s;
        maxTime.update( valToNorm[v[i].f], time );
    }

    cout << maxTime.query( val );

    return 0;
}