Submission #1307894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307894		mikolaj00	Examination (JOI19_examination)	C++20	100 / 100	251 ms	24540 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using ll = long long;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct Sweep
{
    ll x, y, z;
    int idx;

    friend bool operator<(Sweep const& s1, Sweep const& s2)
    {
        return make_pair(s1.z, -s1.idx) > make_pair(s2.z, -s2.idx);
    }
};

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

    int n, q;
    cin >> n >> q;

    vector<ll> s(n), t(n);
    for (int i = 0; i < n; i++)
        cin >> s[i] >> t[i];

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

    vector<Sweep> sweep;
    sweep.reserve(n+q);
    for (int i = 0; i < n; i++)
        sweep.push_back({s[i], t[i], s[i]+t[i], -1});
    for (int i = 0; i < q; i++)
        sweep.push_back({x[i], y[i], z[i], i});
    sort(sweep.begin(), sweep.end());

    vector<ll> ans(q);
    ordered_set<pair<ll, ll>> sx, sy;
    ll id = 0;
    ll num_of_students = 0;

    for (auto s : sweep)
    {
        if (s.idx == -1)
        {
            sx.insert({s.x, id++});
            sy.insert({s.y, id++});
            num_of_students++;
        }
        else
        {
            ll x_bigger = sx.size() - sx.order_of_key({s.x, INT_MIN});
            ll y_bigger = sy.size() - sy.order_of_key({s.y, INT_MIN});
            ans[s.idx] = x_bigger + y_bigger - num_of_students;
        }
    }

    for (auto ans_i : ans)
        cout << ans_i << '\n';
}

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