Submission #1016421

#TimeUsernameProblemLanguageResultExecution timeMemory
1016421fryingducCurtains (NOI23_curtains)C++17
100 / 100
703 ms73040 KiB
#include "bits/stdc++.h" using namespace std; const int maxn = 5e5 + 5; int tree[maxn * 4]; int lazy[maxn * 4]; vector<int> segment[maxn]; vector<pair<int, int>> que[maxn]; int n, m, q; bool ans[maxn]; struct segment_tree { int n; segment_tree() {} segment_tree(int n) : n(n) {} void down(int ind, int l, int r) { tree[ind] = max(tree[ind], lazy[ind]); if(l != r) { lazy[ind * 2] = max(lazy[ind * 2], lazy[ind]); lazy[ind * 2 + 1] = max(lazy[ind * 2 + 1], lazy[ind]); } lazy[ind] = 0; } void update(int ind, int l, int r, int x, int y, int val) { if(lazy[ind]) down(ind, l, r); if(l > y || r < x) return; if(x <= l and r <= y) { lazy[ind] = val; down(ind, l, r); return; } int mid = (l + r) / 2; update(ind * 2, l, mid, x, y, val); update(ind * 2 + 1, mid + 1, r, x, y, val); tree[ind] = min(tree[ind * 2], tree[ind * 2 + 1]); } int get(int ind, int l, int r, int x, int y) { if(lazy[ind]) down(ind, l, r); if(l > y || r < x) return n + 1; if(x <= l and r <= y) return tree[ind]; int mid = (l + r) / 2; return min(get(ind * 2, l, mid, x, y), get(ind * 2 + 1, mid + 1, r, x, y)); } void update(int x, int y, int val) { update(1, 1, n, x, y, val); } int get(int x, int y) { return get(1, 1, n, x, y); } } st; void solve() { cin >> n >> m >> q; for(int i = 1; i <= m; ++i) { int l, r; cin >> l >> r; segment[r].push_back(l); } st = segment_tree(n); for(int i = 1; i <= q; ++i) { int l, r; cin >> l >> r; que[r].push_back({l, i}); } for(int i = 1; i <= n; ++i) { for(auto l:segment[i]) { st.update(l, i, l); } for(auto e:que[i]) { ans[e.second] = (st.get(e.first, i) >= e.first); } } for(int i = 1; i <= q; ++i) { cout << (ans[i] ? "YES\n" : "NO\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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...