Submission #1088724

#TimeUsernameProblemLanguageResultExecution timeMemory
1088724vladiliusCurtains (NOI23_curtains)C++17
100 / 100
832 ms89940 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second const int inf = 5e5 + 1; struct ST{ struct node{ int mn, mn2; }; vector<node> t; vector<int> p; int n; ST(int ns){ n = ns; t.assign(4 * n, {0, inf}); p.resize(4 * n); } void merge(int& v){ int vv = 2 * v; if (t[vv].mn < t[vv + 1].mn){ t[v].mn = t[vv].mn; t[v].mn2 = min(t[vv + 1].mn, t[vv].mn2); } else { t[v].mn = t[vv + 1].mn; t[v].mn2 = min(t[vv].mn, t[vv + 1].mn2); } } void push(int& v){ if (!p[v]) return; int vv = 2 * v; t[vv].mn = max(t[vv].mn, p[v]); t[vv + 1].mn = max(t[vv + 1].mn, p[v]); p[vv] = max(p[vv], p[v]); p[vv + 1] = max(p[vv + 1], p[v]); p[v] = 0; } void chmax(int v, int tl, int tr, int& l, int& r, int& x){ if (l > tr || r < tl || t[v].mn >= x) return; if (l <= tl && tr <= r && t[v].mn2 > x){ t[v].mn = x; p[v] = x; return; } int tm = (tl + tr) / 2, vv = 2 * v; push(v); chmax(vv, tl, tm, l, r, x); chmax(vv + 1, tm + 1, tr, l, r, x); merge(v); } void chmax(int l, int r, int x){ chmax(1, 1, n, l, r, x); } int get(int v, int tl, int tr, int& l, int& r){ if (l > tr || r < tl) return inf; if (l <= tl && tr <= r) return t[v].mn; push(v); int tm = (tl + tr) / 2, vv = 2 * v; return min(get(vv, tl, tm, l, r), get(vv + 1, tm + 1, tr, l, r)); } int get(int l, int r){ return get(1, 1, n, l, r); } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, q; cin>>n>>m>>q; vector<int> st[n + 1]; while (m--){ int l, r; cin>>l>>r; st[r].pb(l); } vector<pii> qs[n + 1]; for (int i = 1; i <= q; i++){ int l, r; cin>>l>>r; qs[r].pb({l, i}); } vector<int> out(q + 1); ST T(n); for (int r = 1; r <= n; r++){ for (int l: st[r]){ T.chmax(l, r, l); } for (auto [l, i]: qs[r]){ out[i] = (T.get(l, r) >= l); } } for (int i = 1; i <= q; i++){ cout<<(out[i] ? "YES" : "NO")<<"\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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...