Submission #1187717

#TimeUsernameProblemLanguageResultExecution timeMemory
1187717oviyan_gandhiExamination (JOI19_examination)C++17
0 / 100
1259 ms250956 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 1000000 struct Score { int x, y, z, i; bool operator < (const Score &o) const { return make_tuple(z, x, y) > make_tuple(o.z, o.x, o.y); } } a[N], qu[N]; int ans[N]; struct SegTree { int rl, rr, mid; SegTree *l, *r; oset<int> st; SegTree(int rl, int rr) : rl{rl}, rr{rr}, mid{(rl+rr)/2}, l{nullptr}, r{nullptr} {} void update(int x, int y) { st.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 st.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; for (int i = 0; i < n; i++) { cin >> a[i].x >> a[i].y; a[i].z = a[i].x + a[i].y; } sort(a, a+n); for (int i = 0; i < q; i++) { cin >> qu[i].x >> qu[i].y >> qu[i].z; qu[i].i = i; } sort(qu, qu+q); SegTree seg(1LL, 20000000000LL); int i = 0; for (int qi = 0; 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 = 0; 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...