Submission #716697

#	Time	Username	Problem	Language	Result	Execution time	Memory
716697		four_specks	Examination (JOI19_examination)	C++17	100 / 100	1291 ms	92284 KiB

examination

#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

namespace
{
    template <typename T, typename Cmp = less<T>>
    using OrderedSet = tree<T, null_type, Cmp, rb_tree_tag, tree_order_statistics_node_update>;

} // namespace

void solve()
{
    int n, q;
    cin >> n >> q;

    vector<array<long, 2>> a(n);
    for (auto &[u, v] : a)
        cin >> u >> v;

    sort(
        a.begin(), a.end(),
        [&](const array<long, 2> &lhs, const array<long, 2> &rhs) -> bool
        { return lhs[0] + lhs[1] > rhs[0] + rhs[1]; });

    vector<long> x(q), y(q), z(q);
    for (int i = 0; i < q; i++)
        cin >> x[i] >> y[i] >> z[i];

    vector<long> all;
    for (int i = 0; i < n; i++)
        all.push_back(a[i][0]);
    for (int i = 0; i < q; i++)
        all.push_back(x[i]);
    sort(all.begin(), all.end());

    int k = (int)all.size();

    auto idx = [&](long u) -> int
    { return (int)(lower_bound(all.begin(), all.end(), u) - all.begin()); };

    vector<int> order(q);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(),
         [&](int i, int j) -> bool
         { return z[i] > z[j]; });

    vector<int> res(q);

    vector<OrderedSet<pair<long, int>>> fenw(k + 1);

    int op = 0;

    auto upd = [&](long u, long v) -> void
    {
        for (int p = k - idx(u); p <= k; p += p & -p)
            fenw[p].insert(pair(-v, op++));
    };

    auto qry = [&](long u, long v) -> int
    {
        int ret = 0;
        for (int p = k - idx(u); p; p -= p & -p)
            ret += (int)fenw[p].order_of_key(pair(-v, op));

        return ret;
    };

    for (int l = 0, i = 0; i < q; i++)
    {
        int j = order[i];

        while (l < n && a[l][0] + a[l][1] >= z[j])
        {
            upd(a[l][0], a[l][1]);
            l++;
        }

        res[j] = qry(x[j], y[j]);
    }

    for (int i = 0; i < q; i++)
        cout << res[i] << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57