제출 #1283574

#제출 시각아이디문제언어결과실행 시간메모리
1283574petezaCurtains (NOI23_curtains)C++20
100 / 100
991 ms45872 KiB
#include <bits/stdc++.h> using namespace std; const int mxn = 500005; int segm[mxn*4], laz[mxn*4]; int n, b, q, l, r; int ans[mxn]; vector<pair<int, int>> qrs[mxn]; void push(int idx, int len) { segm[idx] = max(segm[idx], laz[idx]); if(len > 1) { laz[idx*2+1] = max(laz[idx*2+1], laz[idx]); laz[idx*2+2] = max(laz[idx*2+2], laz[idx]); } laz[idx] = 0; } void upd(int idx, int l, int r, int tl, int tr, int val) { push(idx, r-l+1); if(tr < l || r < tl) return; if(tl <= l && r <= tr) { laz[idx] = val; push(idx, r-l+1); return ; } int mid = (l+r) >> 1; upd(idx*2+1, l, mid, tl, tr, val); upd(idx*2+2, mid+1, r, tl, tr, val); segm[idx] = min(segm[idx*2+1], segm[idx*2+2]); } int qr(int idx, int l, int r, int tl, int tr) { push(idx, r-l+1); if(tr < l || r < tl) return INT_MAX; if(tl <= l && r <= tr) return segm[idx]; int mid = (l+r) >> 1; return min(qr(idx*2+1, l, mid, tl, tr), qr(idx*2+2, mid+1, r, tl, tr)); } int main() { cin.tie(0) -> sync_with_stdio(0); cin >> n >> b >> q; for(int i=1;i<=b;i++) { cin >> l >> r; qrs[r].emplace_back(-1, l); } for(int i=1;i<=q;i++) { cin >> l >> r; qrs[r].emplace_back(i, l); } for(int i=1;i<=n;i++) { sort(qrs[i].begin(), qrs[i].end()); for(auto &e:qrs[i]) { if(e.first == -1) { upd(0, 1, n, e.second, i, e.second+1); } else { //for(int bruh = 1; bruh <= n; bruh++) cout << qr(0, 1, n, bruh, bruh) << ' '; //cout << qr(0, 1, n, e.second, i) << '\n'; ans[e.first] = (e.second < qr(0, 1, n, e.second, i)); } } } for(int i=1;i<=q;i++) cout << (ans[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...