Pagini recente » Cod sursa (job #1767117) | Cod sursa (job #2361743) | Cod sursa (job #2350964) | Cod sursa (job #345936) | Cod sursa (job #3144773)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
pair <int, int> el[100002];
vector <int> g;
int n, rmax, intv, sTot;
void adauga(int x) {
g.push_back (x);
int ic = g.size() - 1;
while (ic / 2 > 0 && g[ic] > g[ic / 2]) {
swap (g[ic], g[ic / 2]);
ic /= 2;
}
}
void elimina() {
g[1] = g[g.size() - 1];
g.pop_back();
unsigned int ic = 1;
unsigned int icop = ic * 2;
while (icop < g.size()) {
icop = ic * 2;
if (icop + 1 <= g.size() - 1 && g[icop] < g[icop + 1])
icop++;
if (icop < g.size() && g[ic] < g[icop]) {
swap (g[ic], g[icop]);
ic = icop;
}
else
icop = g.size();
}
}
int main() {
g.push_back (0);
fin >> n >> rmax >> intv;
for (int i = 1; i <= n; i++) {
fin >> el[i].first >> el[i].second;
el[i].first = (el[i].first + intv - 1) / intv;
}
sort(el + 1, el + n + 1);
int j = 1;
for (int i = 0; i <= (rmax + intv - 1) / intv; i++){
while (el[j].first <= i && j <= n)
adauga (el[j++].second);
if (g.size() - 1) {
sTot += g[1];
elimina();
}
}
fout << sTot;
}