Submission #1260690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260690		tminh	Examination (JOI19_examination)	C++20	0 / 100	1014 ms	48948 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
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>;

#define ll long long
#define pii pair<int,int>

const int MAXN = 200000 + 5;

struct Node {
    ll c;
    int s, t, id; // id==0 => student, else query id
    Node(ll _c, int _s, int _t, int _id): c(_c), s(_s), t(_t), id(_id) {}
    bool operator<(const Node &o) const {
        if (c == o.c) return id < o.id; // students id==0 -> come before queries with same c
        return c > o.c; // larger c first
    }
};

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

    int n, q;
    if (!(cin >> n >> q)) return 0;
    vector<pii> a(n);
    vector<int> arr; arr.reserve(n);
    vector<Node> sw; sw.reserve(n + q);

    for (int i = 0; i < n; ++i){
        cin >> a[i].first >> a[i].second;
        arr.push_back(a[i].first);
        sw.emplace_back( (ll)a[i].first + a[i].second, a[i].first, a[i].second, 0 );
    }

    for (int i = 1; i <= q; ++i){
        int x,y,z;
        cin >> x >> y >> z;
        sw.emplace_back((ll)z, x, y, i);
    }

    // coordinate compress S values
    sort(arr.begin(), arr.end());
    arr.erase(unique(arr.begin(), arr.end()), arr.end());
    int m = (int)arr.size();

    // Fenwick of ordered_sets, size m (1-based)
    vector< ordered_set<int> > bit(m + 1);

    auto add = [&](int s_val, int t_val){
        int idx = lower_bound(arr.begin(), arr.end(), s_val) - arr.begin() + 1; // 1-based
        for (; idx <= m; idx += idx & -idx) bit[idx].insert(t_val);
    };

    auto prefix_count = [&](int s_val, int t_val){
        // count elements with S <= s_val and T >= t_val
        int idx = upper_bound(arr.begin(), arr.end(), s_val) - arr.begin(); // number of S <= s_val
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) {
            res += ( (int)bit[idx].size() - bit[idx].order_of_key(t_val) );
        }
        return res;
    };

    auto range_count = [&](int l_s, int r_s, int t_val){
        if (l_s > r_s) return 0;
        return prefix_count(r_s, t_val) - prefix_count(l_s - 1, t_val);
    };

    sort(sw.begin(), sw.end());
    vector<int> ans(q + 1, 0);

    for (auto &nd : sw){
        if (nd.id == 0) {
            // student: add (S, T)
            add(nd.s, nd.t);
        } else {
            // query: count S in [A, +inf] and T >= B, only students with S+T >= C were added
            int A = nd.s, B = nd.t;
            // r_s = max S present = arr.back() if arr not empty
            if (m == 0) { ans[nd.id] = 0; continue; }
            ans[nd.id] = range_count(A, arr.back(), B);
        }
    }

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

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