제출 #1187691

#제출 시각아이디문제언어결과실행 시간메모리
1187691oviyan_gandhiExamination (JOI19_examination)C++17
20 / 100
678 ms150944 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 pair<int, int> a[N]; oset<int> seg[4*N]; void build(int l, int r, int pos) { for (int i = l; i <= r; i++) seg[pos].insert(a[i].second); if (l == r) return; int mid = (l+r)/2; build(l, mid, 2*pos); build(mid+1, r, 2*pos+1); } int query(int qx, int qy, int l, int r, int pos) { if (a[r].first < qx) return 0; if (a[l].first >= qx) return seg[pos].order_of_key(qy-1); int mid = (l+r)/2; return query(qx, qy, l, mid, 2*pos) + query(qx, qy, mid+1, r, 2*pos+1); } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, q; cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second; sort(a+1, a+n+1); build(1, n, 1); while (q--) { int x, y, z; cin >> x >> y >> z; cout << query(x, y, 1, n, 1) << '\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...