Cod sursa(job #1438274)

Utilizator DEFINEtelyEngineersUPB Pirtoaca Vasilescu Zamfiratos DEFINEtelyEngineers Data 19 mai 2015 15:41:04
Problema Lupul Urias si Rau Scor 24
Compilator cpp Status done
Runda last_acm_practice Marime 1.98 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define Nmax 100005

std::ifstream in("lupu.in");
std::ofstream out("lupu.out");

std::vector<std::pair<int, int> > V;
int AI[4 * Nmax];


void update(int node, int left, int right, int position, int value) {

    if (left == right) {
        AI[node] = value;
        return;
    }

    int middle = (left + right) / 2;
    if (position <= middle) update(node * 2, left, middle, position, value);
    else update(node * 2 + 1, middle + 1, right, position, value);

    AI[node] = AI[node * 2] + AI[node * 2 + 1];
}

int query(int node, int left, int right, int a, int b) {

    if (a <= left && right <= b)
        return AI[node];

    int middle = (left + right) / 2, result = 0;

    if (a <= middle) result = query(node * 2, left, middle, a, b);
    if (middle < b) result += query(node * 2 + 1, middle + 1, right, a, b);

    return result;
}

int find(int node, int left, int right, int x, int s) {

    if (left == right) return left;

    int middle = (left + right) / 2;

    if (x <= middle) return find(node * 2, left, middle, x, s);

    if (AI[node * 2] + AI[node * 2 + 1] < s)
        return find(node * 2 + 1, middle + 1, right, x, s - AI[node * 2]);
    return find(node * 2 + 1, middle + 1, right, x, s);
}

int main() {

    int N, X, L;
    in >> N >> X >> L;

    for (int i = 1; i <= N; i++) {
        int x, y;
        in >> x >> y;

        V.push_back(std::make_pair(y, x));
    }

    std::sort(V.begin(), V.end());

    int total = 0;
    int AIlen = X / L + 1;

    for (int i = V.size() - 1; i >= 0; i--) {
        int value = V[i].first;
        int time = (X - V[i].second) / L + 1;

        if (time <= 0) continue;

        int pp = query(1, 1, AIlen, 1, time);
        if (query(1, 1, AIlen, 1, time) == time) continue;

        int position = find(1, 1, AIlen, time, time - 1);
        update(1, 1, AIlen, position, 1);

        total += value;
    }

    out << total << "\n";
    std::cout << total << "\n";
}