Submission #1261547

#TimeUsernameProblemLanguageResultExecution timeMemory
1261547hoa208Examination (JOI19_examination)C++20
100 / 100
370 ms39808 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; struct Point { int s; int t_idx; // compressed index of T in allV (1-based) ll w; // s + t int t_orig; // original T (not strictly needed) }; struct Query { int X; int Y; ll Z; int idx; // original index int y_idx; // compressed index of Y in allV (1-based) }; struct FenwickSimple { // 1-indexed Fenwick for integers int n; vector<int> bit; FenwickSimple() {} FenwickSimple(int n_): n(n_), bit(n_+1, 0) {} void add(int i, int delta) { for (; i <= n; i += i & -i) bit[i] += delta; } int sumPrefix(int i) { int s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, Q; if (!(cin >> N >> Q)) return 0; vector<pair<int,int>> pts(N); for (int i = 0; i < N; ++i) cin >> pts[i].first >> pts[i].second; vector<tuple<int,int,ll>> queries_input(Q); vector<Query> queries(Q); for (int j = 0; j < Q; ++j) { int X, Y; long long Z; cin >> X >> Y >> Z; queries_input[j] = {X, Y, Z}; queries[j].X = X; queries[j].Y = Y; queries[j].Z = Z; queries[j].idx = j; } // 1) coordinate compress all T's and all Y's vector<int> allV; allV.reserve(N + Q); for (int i = 0; i < N; ++i) allV.push_back(pts[i].second); for (int j = 0; j < Q; ++j) allV.push_back(queries[j].Y); sort(allV.begin(), allV.end()); allV.erase(unique(allV.begin(), allV.end()), allV.end()); int M = (int)allV.size(); // Build Points with compressed t_idx and w vector<Point> points(N); for (int i = 0; i < N; ++i) { int s = pts[i].first; int t = pts[i].second; int t_idx = int(lower_bound(allV.begin(), allV.end(), t) - allV.begin()) + 1; // 1-based points[i].s = s; points[i].t_idx = t_idx; points[i].w = (ll)s + (ll)t; points[i].t_orig = t; } // set y_idx for queries (first index with value >= Y) for (int j = 0; j < Q; ++j) { int Y = queries[j].Y; int y_idx = int(lower_bound(allV.begin(), allV.end(), Y) - allV.begin()) + 1; // 1-based // if Y is greater than all values, y_idx will be M+1. That's OK. queries[j].y_idx = y_idx; } // 2) Prepare bit nodes: for each point, push w into nodes i = t_idx .. M stepping by i&-i vector<vector<ll>> node_vals(M+1); for (int i = 0; i < N; ++i) { int idx = points[i].t_idx; ll w = points[i].w; for (int p = idx; p <= M; p += p & -p) node_vals[p].push_back(w); } // sort & unique each node's values and prepare FenwickSimple for each node vector<FenwickSimple> node_bit(M+1); vector<int> node_total(M+1, 0); // number of inserts done in that node for (int i = 1; i <= M; ++i) { auto &v = node_vals[i]; if (!v.empty()) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); node_bit[i] = FenwickSimple((int)v.size()); } } // 3) Sort points by s descending and queries by X descending sort(points.begin(), points.end(), [](const Point &a, const Point &b){ return a.s > b.s; }); sort(queries.begin(), queries.end(), [](const Query &a, const Query &b){ return a.X > b.X; }); // helper functions: update a point (t_idx, w) into BIT-of-v auto update_point = [&](int t_idx, ll w) { for (int p = t_idx; p <= M; p += p & -p) { auto &vals = node_vals[p]; if (vals.empty()) continue; int pos = int(lower_bound(vals.begin(), vals.end(), w) - vals.begin()); // 0-based // update FenwickSimple at pos+1 by +1 node_bit[p].add(pos+1, 1); node_total[p] += 1; } }; // query prefix up to idx (v <= idx), count w >= Z auto query_prefix = [&](int idx, ll Z) -> int { if (idx <= 0) return 0; if (idx > M) idx = M; int res = 0; for (int p = idx; p > 0; p -= p & -p) { auto &vals = node_vals[p]; if (vals.empty()) continue; int pos = int(lower_bound(vals.begin(), vals.end(), Z) - vals.begin()); // number of values < Z int pref = node_bit[p].sumPrefix(pos); // count of w < Z // suffix = total - pref = count of w >= Z res += (node_total[p] - pref); } return res; }; vector<int> ans(Q, 0); int cur_pt = 0; // index in points (sorted desc by s) for (int qi = 0; qi < Q; ++qi) { const Query &q = queries[qi]; int X = q.X; // insert all points with s >= X while (cur_pt < N && points[cur_pt].s >= X) { update_point(points[cur_pt].t_idx, points[cur_pt].w); ++cur_pt; } int y_idx = q.y_idx; // if y_idx is M+1 (Y greater than any compressed value), then no v >= Y exists -> answer 0 if (y_idx > M) { ans[q.idx] = 0; continue; } int total_up_to_M = query_prefix(M, q.Z); int up_to_before_y = query_prefix(y_idx - 1, q.Z); ans[q.idx] = total_up_to_M - up_to_before_y; } // print answers in original order for (int j = 0; j < Q; ++j) cout << ans[j] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...