Pagini recente » Istoria paginii runda/oji_2019_10/clasament | Cod sursa (job #701532) | Cod sursa (job #2893892) | Cod sursa (job #1788948) | Cod sursa (job #2785398)
#include <fstream>
#include <algorithm>
#define NMAX 100000
#pragma optimize ("o3")
using namespace std;
ifstream cin ("lupu.in");
ofstream cout ("lupu.out");
struct hatz {
int lana, repets;
};
int n;
int vaib[NMAX + 1];
bool vf[NMAX + 1];
hatz v[NMAX + 1];
bool cmp(hatz A, hatz B) {
if (A.lana == B.lana)
return A.repets > B.repets;
return A.lana > B.lana;
}
static inline int lsb(int val) {
return val & (-val);
}
void update(int poz, int val) {
while (poz <= n) {
vaib[poz] += val;
poz += lsb(poz);
}
}
int query1(int poz) { /// returneaza suma (1,poz)
int sol = 0;
while (poz > 0) {
sol += vaib[poz];
poz -= lsb(poz);
}
return sol;
}
int query2(int st, int dr) {
int mij, sol;
sol = -1;
while (st <= dr) {
mij = (st + dr) / 2;
if (vf[mij] == 0)
sol = mij;
if (query1(dr) - query1(mij - 1) < dr - mij + 1)
st = mij + 1;
else {
dr = mij - 1;
if (sol > -1)
return sol;
}
}
return sol;
}
int getnr() {
int nr;
char ch;
ch = cin.get();
while (!(ch >= '0' && ch <= '9'))
ch = cin.get();
nr = 0;
while (ch >= '0' && ch <= '9') {
nr = nr * 10 + ch - '0';
ch = cin.get();
}
return nr;
}
int main(){
int x, l, i, a, poz;
long long sol;
cin >> n >> x >> l;
for (i = 1; i <= n; ++i) {
a = getnr();
v[i].lana = getnr();
if (v[i].lana >= (1LL << 25))
return 1;
if (x >= a)
v[i].repets = (x - a) / l + 1;
else
v[i].repets = -1;
}
sort(v + 1, v + n + 1, cmp);
sol = 0;
for (i = 1; i <= n; i++) {
if (v[i].repets > 0) {
poz = query2(1, v[i].repets);
if (poz > -1) {
vf[poz] = 1;
update(poz, 1);
sol += v[i].lana;
}
}
}
cout << sol;
return 0;
}