Pagini recente » Cod sursa (job #708971) | Cod sursa (job #2519843) | Monitorul de evaluare | Cod sursa (job #1595796) | Cod sursa (job #2785663)
#include <stdio.h>
#include <algorithm>
#define MAX_N 100000
using std::sort;
struct oaie {
int timp, lana;
bool operator < (const oaie &b ) const {
if ( lana == b.lana )
return timp > b.timp;
return lana > b.lana;
}
};
int aib[MAX_N];
oaie v[MAX_N];
int query( int i ) {
int x;
x = 0;
while ( i > 0 ) {
x += aib[i];
i -= (i & -i);
}
return x;
}
void update( int i, int x, int n ) {
while ( i <= n ) {
aib[i] += x;
i += (i & -i);
}
}
int main() {
FILE *fin, *fout;
int n, d, l, dist, st, dr, mij, i;
long long sumaLana;
fin = fopen( "lupu.in", "r" );
fscanf( fin, "%d%d%d", &n, &d, &l );
for ( i = 0; i < n; i++ ) {
fscanf( fin, "%d%d", &dist, &v[i].lana );
v[i].timp = (d - dist) / l + 1;
v[i].timp = v[i].timp < n ? v[i].timp : n;
}
fclose( fin );
sort( v, v + n );
sumaLana = 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( mij ) - (v[i].timp - mij) < query( v[i].timp ) )
st = mij;
else
dr = mij;
}
if ( query( dr ) == query( st ) ) {
sumaLana += v[i].lana;
}
update( dr, 1, n );
}
}
fout = fopen( "lupu.out", "w" );
fprintf( fout, "%lld", sumaLana );
fclose( fout );
return 0;
}