Pagini recente » Cod sursa (job #793021) | Cod sursa (job #846805) | Cod sursa (job #2543726) | Cod sursa (job #755734) | Cod sursa (job #2806729)
#include <fstream>
#include <algorithm>
#pragma GCC optimize("O3")
#pragma GCC optimize("AVL")
#pragma GCC optimize("AVX")
using namespace std;
ifstream cin ( "lupu.in" );
ofstream cout ( "lupu.out" );
#define NMAX 100000
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;
}
int 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;
}