Cod sursa(job #960620)

Utilizator primulDarie Sergiu primul Data 10 iunie 2013 20:25:14
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#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;
}