제출 #1323539

#제출 시각아이디문제언어결과실행 시간메모리
1323539aryanCurtains (NOI23_curtains)C++20
100 / 100
657 ms27724 KiB
#include<bits/stdc++.h> using namespace std; using i64 = long long; const int inf = 1e9; const int N = 5e5 + 5; vector<int> tree(4 * N,inf); vector<int> lazy(4 * N,inf); void dolazy(int ind){ tree[2 * ind] = min(tree[2 * ind],lazy[ind]); tree[2 * ind + 1] = min(tree[2 * ind + 1],lazy[ind]); lazy[2 * ind] = min(lazy[2 * ind],lazy[ind]); lazy[2 * ind + 1] = min(lazy[2 * ind + 1],lazy[ind]); } void update(int ind,int nl,int nr,int l,int r){ if(nl > r || l > nr) return; if(l <= nl && r >= nr){ tree[ind] = min(tree[ind],r); lazy[ind] = min(lazy[ind],r); return; } dolazy(ind); int mid = (nl + nr) / 2; update(2 * ind,nl,mid,l,r); update(2 * ind + 1,mid + 1,nr,l,r); tree[ind] = max(tree[2 * ind],tree[2 * ind + 1]); } int query(int ind,int nl,int nr,int l,int r){ if(nl > r || l > nr) return 0; if(l <= nl && r >= nr){ return tree[ind]; } dolazy(ind); int mid = (nl + nr) / 2; return max(query(2 * ind,nl,mid,l,r), query(2 * ind + 1,mid + 1,nr,l,r)); } struct Data{ int l,r,i; Data() {}; bool operator <(Data &d){ return d.l < this->l; } }; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m,q; cin >> n >> m >> q; vector<pair<int,int>> rn(m); for(int i = 0;i < m;i++){ cin >> rn[i].first >> rn[i].second; } sort(rn.begin(),rn.end(),greater<pair<int,int>>()); vector<Data> que(q); for(int i = 0;i < q;i++){ cin >> que[i].l >> que[i].r; que[i].i = i; } sort(que.begin(),que.end()); vector<bool> ans(q); int j = 0; for(int i = 0;i < q;i++){ while(j < m && que[i].l <= rn[j].first){ update(1,0,n,rn[j].first,rn[j].second); j ++; } if(query(1,0,n,que[i].l,que[i].r) > que[i].r){ ans[que[i].i] = false; }else{ ans[que[i].i] = true; } } for(int i = 0;i < q;i++){ cout << (ans[i] ? "YES\n" : "NO\n"); } 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...