Submission #1014329

#TimeUsernameProblemLanguageResultExecution timeMemory
1014329fryingducExamination (JOI19_examination)C++17
100 / 100
414 ms32240 KiB
#include "bits/stdc++.h" using namespace std; const int maxn = 1e5 + 5; const int inf = 1e9; int n, q, s[maxn], t[maxn]; int a[maxn], b[maxn]; int ord[maxn]; vector<int> bit[maxn]; int ans[maxn]; struct query { int x, y, z, id; bool operator<(const query &o) { return z > o.z; } } que[maxn]; vector<int> cx, cy; #define gb(x) (x) & (-x) struct fenwick_tree { int n; vector<int> bit; fenwick_tree() {} fenwick_tree(int n) : n(n), bit(n + 5) {} inline void update(int x, int val) { for(int i = x; i <= n; i += gb(i)) bit[i] = bit[i] + val; } inline int get(int x) { int ans = 0; for(int i = x; i > 0; i -= gb(i)) ans = ans + bit[i]; return ans; } } tree[maxn]; vector<int> sz[maxn]; struct segment_tree { int n; segment_tree() {} segment_tree(int n) : n(n) {} inline void resize_tree(int pos, int fen_pos) { for(int i = pos; i <= n; i += gb(i)) { sz[i].push_back(fen_pos); } } inline void refine() { for(int ind = 1; ind <= n; ++ind) { if(sz[ind].empty()) continue; sort(sz[ind].begin(), sz[ind].end()); sz[ind].erase(unique(sz[ind].begin(), sz[ind].end()), sz[ind].end()); tree[ind] = fenwick_tree((int)sz[ind].size() + 2); } } inline void update(int pos, int fen_pos, int val) { int p; for(int i = pos; i <= n; i += gb(i)) { p = lower_bound(sz[i].begin(), sz[i].end(), fen_pos) - sz[i].begin() + 1; tree[i].update(p, val); } } inline int get(int pos, int fen_pos) { int ans = 0; int p; for(int i = pos; i > 0; i -= gb(i)) { p = upper_bound(sz[i].begin(), sz[i].end(), fen_pos) - sz[i].begin(); if(p == 0) continue; ans = ans + tree[i].get(p); } return ans; } int get(int l, int r, int pos) { return get(r, pos) - get(l - 1, pos); } } st; void solve() { cin >> n >> q; for(int i = 1; i <= n; ++i) { cin >> s[i] >> t[i]; } for(int i = 1; i <= q; ++i) { cin >> que[i].x >> que[i].y >> que[i].z; que[i].id = i; } iota(ord + 1, ord + n + 1, 1); sort(ord + 1, ord + n + 1, [](const int &x, const int &y) -> bool { return (s[x] + t[x]) > (s[y] + t[y]); }); for(int i = 1; i <= n; ++i) { cx.push_back(s[i]); cy.push_back(t[i]); } sort(cx.begin(), cx.end()); sort(cy.begin(), cy.end()); cx.erase(unique(cx.begin(), cx.end()), cx.end()); cy.erase(unique(cy.begin(), cy.end()), cy.end()); st = segment_tree((int)cx.size()); for(int i = 1; i <= n; ++i) { a[i] = lower_bound(cx.begin(), cx.end(), s[i]) - cx.begin() + 1; b[i] = lower_bound(cy.begin(), cy.end(), t[i]) - cy.begin() + 1; st.resize_tree(a[i], t[i]); } st.refine(); sort(que + 1, que + q + 1); int j = 1; for(int i = 1; i <= q; ++i) { while(j <= n and s[ord[j]] + t[ord[j]] >= que[i].z) { st.update(a[ord[j]], t[ord[j]], 1); ++j; } int p = lower_bound(cx.begin(), cx.end(), que[i].x) - cx.begin() + 1; ans[que[i].id] = st.get(p, (int)cx.size(), inf); ans[que[i].id] -= st.get(p, (int)cx.size(), que[i].y - 1); } for(int i = 1; i <= q; ++i) { cout << ans[i] << '\n'; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); solve(); 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...