Pagini recente » Cod sursa (job #2265003) | Cod sursa (job #1398419) | Cod sursa (job #2977133) | Cod sursa (job #2121608) | Cod sursa (job #959662)
Cod sursa(job #959662)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
#define in "lupu.in"
#define out "lupu.out"
#define N 100005
#define hs H.size()-1
typedef pair <int, int> data;
vector <int> H;
int n, X, l;
long long sol;
data v[N];
void insert(int x) {
H.push_back (x);
int k = hs;
while (k / 2 > 0 && H[k] > H[k / 2]) {
swap (H[k], H[k / 2]);
k /= 2;
}
}
void eject() {
H[1] = H[hs];
H.pop_back();
unsigned k = 1, kk = k * 2;
while (kk <= hs) {
kk = k * 2;
if (kk + 1 <= hs && H[kk] < H[kk + 1])
kk++;
if (kk <= hs && H[k] < H[kk]) {
swap (H[k], H[kk]);
k = kk;
}
else
kk = hs + 1;
}
}
int main() {
H.push_back (0);
ifstream fin (in);
fin >> n >> X >> l;
for (int i = 0; i < n; ++i) {
fin >> v[i].first >> v[i].second;
v[i].first = (v[i].first + l - 1) / l;
}
sort (v, v+n);
int j = 0;
for (int i = 0; i <= (X + l - 1) / l; ++i) {
while (v[j].first <= i && j < n)
insert (v[j++].second);
if (hs) {
sol += H[1];
eject();
}
}
ofstream fout (out);
fout << sol;
fout.close();
return 0;
}