Submission #1187701

#TimeUsernameProblemLanguageResultExecution timeMemory
1187701oviyan_gandhiExamination (JOI19_examination)C++17
0 / 100
1022 ms140712 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define int long long using namespace std; using namespace __gnu_pbds; template <typename T> using oset = tree<T, null_type, greater_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; #define N 100001 struct Score { int x, y, z, i; bool operator < (const Score &o) const { return z > o.z; } } a[N], qu[N]; int ans[N]; struct SegTree { int rl, rr, mid; SegTree *l, *r; oset<int> seg; SegTree(int rl, int rr) : rl{rl}, rr{rr}, mid{(rl+rr)/2}, l{nullptr}, r{nullptr} {} ~SegTree() { delete l; delete r; } void update(int x, int y) { seg.insert(y); if (rl == rr) return; if (x <= mid) { if (l == nullptr) l = new SegTree(rl, mid); l->update(x, y); } else { if (r == nullptr) r = new SegTree(mid+1, rr); r->update(x, y); } } int query(int x, int y) { if (rr < x) return 0; if (x <= rl) return seg.order_of_key(y-1); int ans = 0; if (l != nullptr) ans += l->query(x, y); if (r != nullptr) ans += r->query(x, y); return ans; } }; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, q; cin >> n >> q; int mx = 0; for (int i = 1; i <= n; i++) { cin >> a[i].x >> a[i].y; a[i].z = a[i].x + a[i].y; mx = max(mx, a[i].x); } sort(a+1, a+n+1); for (int i = 1; i <= q; i++) { cin >> qu[i].x >> qu[i].y >> qu[i].z; qu[i].i = i; mx = max(mx, qu[i].x); } sort(qu+1, qu+q+1); SegTree seg(1, mx); int i = 1; for (int qi = 1; qi <= q; qi++) { for (; i <= n && a[i].z >= qu[qi].z; i++) seg.update(a[i].x, a[i].y); ans[qu[qi].i] = seg.query(qu[qi].x, qu[qi].y); } for (int i = 1; i <= q; i++) cout << ans[i] << '\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...