Cod sursa(job #2531713)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 26 ianuarie 2020 17:21:38
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100005;

int N;
vector < pair<int,int> > V;

int nr_l;
int tree[4 * NMAX];

void Read()
{
    fin >> N;

    V.push_back( { 0, 0 } );

    for( int i = 1; i <= N; ++i ) {
        int a, b;
        fin >> a >> b;

        V.push_back( { b, a } );
    }
}

void Update( int nod, int lf, int rg, int pos, int val )
{
    if( lf == rg ) {
        tree[nod] = val;
        return;
    }

    int mid = lf + ( rg - lf ) / 2;

    if( pos <= mid ) Update( nod * 2, lf, mid, pos, val );
    else Update( nod * 2 + 1, mid + 1, rg, pos, val );

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

int Query( int nod, int lf, int rg, int L, int R ) {
    if( L <= lf && rg <= R ) return tree[nod];

    int mid = lf + ( rg - lf ) / 2;
    int ans = 0;

    if( L <= mid ) ans = Query( nod * 2, lf, mid, L, R );
    if( mid < R )  ans = max( ans, Query( nod * 2 + 1, mid + 1, rg, L, R ) );

    return ans;
}

int BinSearch( int lf, int rg, int val ) {
    if( lf > rg ) return -1;

    int mid = lf + ( rg - lf ) / 2;

    if( V[mid].first <= val ) return max( mid, BinSearch( mid + 1, rg, val ) );
    else return BinSearch( lf, mid - 1, val );
}

void Do()
{
    sort( V.begin(), V.end() );

    for( int i = 1; i <= N; ++i )
    {
       if( i == 1 || V[i].second < V[1].first ) Update( 1, 1, N, i, V[i].first - V[i].second );
       else {
         int p = BinSearch( 1, i - 1, V[i].second );



         Update( 1, 1, N, i, V[i].first - V[i].second + Query( 1, 1, N, 1, p ) );
       }
    }

    fout << Query( 1, 1, N, 1, N ) << '\n';
}

int main()
{
    Read();
    Do();

    return 0;
}