Cod sursa(job #2806731)

Utilizator AlexNicuNicu Alexandru AlexNicu Data 22 noiembrie 2021 22:29:06
Problema Lupul Urias si Rau Scor 28
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#include <algorithm>
#pragma GCC optimize("O3")

using namespace std;

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

#define NMAX 100000
#define int long long

struct OITA {
    int timp, lana;
    bool operator < ( const OITA& other ) const {
        if ( timp == other.timp )
            return lana > other.lana;
        return timp < other.timp;
    }
};

OITA v[NMAX + 1];
int aib[NMAX + 1], n;

void update( int poz, int val ) {
    while ( poz < n ) {
        aib[poz] += val;
        int p2 = poz & ( -poz );
        poz += p2;
    }
}

int query( int poz ) {
    int ans;
    ans = 0;
    while ( poz > 0 ) {
        ans += aib[poz];
        int p2 = poz & ( -poz );
        poz -= p2;
    }
    return ans;
}

signed main() {
    int x, l, i, st, dr, mij, ans;
    ios_base::sync_with_stdio(true);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> x >> l;
    for ( i = 0; i < n; i++ ) {
        cin >> v[i].timp >> v[i].lana;
        v[i].timp = ( x - v[i].timp ) / l + 1;
        v[i].timp = min ( n, v[i].timp );
    }
    sort ( v, v + n );
    ans = 0;
    for ( i = 0; i < n; i++ ) {
        if ( v[i].timp >= 1 ) {
            st = 0;
            dr = v[i].timp;
            while ( dr - st > 1 ) {
                mij = ( st + dr ) / 2;
                if ( query(v[i].timp) - query(mij) < v[i].timp - mij ) {
                    st = mij;
                }
                else
                    dr = mij;
            }
            if ( query(st) == query(dr) ) {
                ans += v[i].lana;
                update( dr, 1 );
            }
        }
    }
    cout << ans;
    return 0;
}