Submission #965751

#TimeUsernameProblemLanguageResultExecution timeMemory
965751Trisanu_DasCurtains (NOI23_curtains)C++17
100 / 100
593 ms75280 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e6 + 7; const int inf = 1e9 + 7; struct SEGT{ int tree[N]; SEGT(){ for(int i = 0;i<N;i++) tree[i] = inf; } void update(int ind , int l , int r , int ql , int qr){ if(l >= ql and r <= qr){ tree[ind] = min(tree[ind] , qr); return; } else if(l > qr or r < ql) return; else{ int mid = (l+r)/2; update(ind*2,l,mid,ql,qr); update(ind*2+1,mid+1,r,ql,qr); tree[ind] = min(tree[ind] , max(tree[ind*2] , tree[ind*2+1])); } } bool query(int ind , int l , int r , int ql , int qr){ if(l >= ql and r <= qr) return tree[ind] <= qr; else if(l > qr or r < ql) return 1; else{ int mid = (l+r)/2; return query(ind*2,l,mid,ql,qr) and query(ind*2+1,mid+1,r,ql,qr); } } } segt; void solve(){ int n,m,q; cin >> n >> m >> q; vector < int > ran[n+1]; vector < pair < int , int > > query[n+1]; for(int i = 0;i<m;i++){ int x,y; cin >> x >> y; ran[x].push_back(y); } for(int i = 0;i<q;i++){ int x,y; cin >> x >> y; query[x].push_back({y,i}); } int ans[q]; for(int i = n;i>0;i--){ for(auto itr : ran[i]) segt.update(1,1,n,i,itr); for(auto itr : query[i]) ans[itr.second] = segt.query(1,1,n,i,itr.first); } for(int i = 0;i<q;i++) cout << (ans[i] ? "YES\n" : "NO\n"); } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); solve(); }
#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...