oj.uz

Submission #716696

# Submission time Handle Problem Language Result Execution time Memory
716696 2023-03-30T20:02:11 Z four_specks Examination (JOI19_examination) C++17
0 / 100
 1233 ms 86564 KB 
#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) - 1; 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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 12 ms 2388 KB Output is correct
8 Correct 9 ms 2404 KB Output is correct
9 Correct 9 ms 2388 KB Output is correct
10 Correct 8 ms 2388 KB Output is correct
11 Incorrect 8 ms 2516 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1233 ms 86564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1233 ms 86564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 12 ms 2388 KB Output is correct
8 Correct 9 ms 2404 KB Output is correct
9 Correct 9 ms 2388 KB Output is correct
10 Correct 8 ms 2388 KB Output is correct
11 Incorrect 8 ms 2516 KB Output isn't correct
12 Halted 0 ms 0 KB -