Cod sursa(job #2970587)

Utilizator user12345user user user user12345 Data 25 ianuarie 2023 16:26:52
Problema Lupul Urias si Rau Scor 16
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
#include<bits/stdc++.h>
using namespace std;

ifstream fin("lupu.in");
ofstream fout("lupu.out");

int n, bound, stage;
pair <int, int> v[100001];
pair <int, int> t[500001];

void build(int i, int l, int r)
{
    if (l == r)
    {
        t[i] = { v[i].second, l };
        return;
    }

    int m = (l + r) >> 1;

    build(2 * i, l, m);
    build(2 * i + 1, m + 1, r);

    if (t[2 * i].first >= t[2 * i + 1].first)
        t[i] = t[2 * i];
    else
        t[i] = t[2 * i + 1];
}

void update(int i, int l, int r, int poz)
{
    if (l == r)
        return;

    int m = (l + r) >> 1;

    if (poz <= m)
        update(2 * i, l, m, poz);
    else
        update(2 * i + 1, m + 1, r, poz);

    if (t[2 * i].first >= t[2 * i + 1].first)
        t[i] = t[2 * i];
    else
        t[i] = t[2 * i + 1];
}

pair <int, int> maxim(int i, int l, int r, int x, int y)
{
    if (y < l || r < x)
        return { 0, 0 };

    if (x <= l && r <= y)
        return t[i];

    int m = (l + r) / 2;

    return max(maxim(2 * i, l, m, x, y), maxim(2 * i + 1, m + 1, r, x, y));
}

int main()
{
    fin >> n >> bound >> stage;

    if (!stage)
    {
        long long total = 0;

        for (int i = 1; i <= n; i++)
            fin >> v[i].first >> v[i].second, total += (v[i].first <= bound ? v[i].second : 0);

        fout << total;
        return 0;
    }

    for (int i = 1; i <= n; i++)
        fin >> v[i].first >> v[i].second;

    sort(v + 1, v + n + 1);
    build(1, 1, n);

    int k = n;

    while (k && v[k].first > bound)
        k--;

    long long total = 0;

    while (bound >= 0 && k)
    {
        bound -= stage;
        int maxVal = 0;

        while (k && v[k].first > bound)
            maxVal = max(maxVal, v[k--].second);

        if (maxVal)
            total += maxVal;
        else if (k)
        {
            pair <int, int> p = maxim(1, 1, n, 1, k);
            total += p.first;
            v[p.second].second = 0;
        }
    }

    fout << total;

    return 0;
}