Submission #255095

#TimeUsernameProblemLanguageResultExecution timeMemory
255095arujbansalExamination (JOI19_examination)C++17
2 / 100
3054 ms27896 KiB
#include <bits/stdc++.h> #define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr) #define FILE_IO freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #define trav(e, x) for (auto &e : x) #define pb(x) push_back(x) #define eb(x...) emplace_back(x) #define all(x) x.begin(), x.end() #define sz(x) (int) (x).size() #define lc(i) 2*i+1 #define rc(i) 2*i+2 #define int long long using namespace std; typedef pair<int, int> ii; struct pupil { pair<int, int> math, info, total; int dep; }; bool comp(pupil x, pupil y) { if (x.info.first != y.info.first) return x.info.first < y.info.first; if (x.math.first != y.math.first) return x.math.first < y.math.first; return x.total.first < y.total.first; } struct SegmentTree { int n; vector<pupil> tree; void init(int x) { n = x; tree.resize(4 * n); } static pupil merge(pupil x, pupil y) { pupil ans; ans.math.first = min(x.math.first, y.math.first); ans.math.second = max(x.math.second, y.math.second); ans.info.first = min(x.info.first, y.info.first); ans.info.second = max(x.info.second, y.info.second); ans.total.first = min(x.total.first, y.total.first); ans.total.second = max(x.total.second, y.total.second); ans.dep = x.dep + y.dep; return ans; } void build(int i, int l, int r, vector<pupil> &a) { if (l == r) tree[i] = a[l]; else { int mid = (l + r) / 2; build(lc(i), l, mid, a); build(rc(i), mid + 1, r, a); tree[i] = merge(tree[lc(i)], tree[rc(i)]); } } int query(int i, int l, int r, int math, int info, int total) { //cout << i << "\n"; if (tree[i].math.second < math || tree[i].info.second < info || tree[i].total.second < total) return 0; if (tree[i].math.first >= math && tree[i].info.first >= info && tree[i].total.first >= total) return tree[i].dep; int mid = (l + r) / 2; return query(lc(i), l, mid, math, info, total) + query(rc(i), mid + 1, r, math, info, total); } void build(vector<pupil> &a) { build(0, 0, n - 1, a); } int query(int math, int info, int total) { return query(0, 0, n - 1, math, info, total); } }; signed main() { FAST_IO; //FILE_IO; int n, q; cin >> n >> q; vector<pupil> students(n); for (int i = 0; i < n; i++) { cin >> students[i].math.first >> students[i].info.first; students[i].math.second = students[i].math.first; students[i].info.second = students[i].info.first; students[i].total.first = students[i].total.second = students[i].math.first + students[i].info.first; students[i].dep = 1; } //sort(all(students), comp); SegmentTree tree; tree.init(n); tree.build(students); //cout << tree.tree[0].math.second << " " << tree.tree[0].info.second << " " << tree.tree[0].total.second << " "; while (q--) { int x, y, z; cin >> x >> y >> z; cout << tree.query(x, y, z) << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...