제출 #1323464

#제출 시각아이디문제언어결과실행 시간메모리
1323464aryanCurtains (NOI23_curtains)C++20
45 / 100
1599 ms173420 KiB
#include<bits/stdc++.h> using namespace std; using i64 = long long; const int N = 1e5; vector<int> tree(4 * N,N + 5); vector<multiset<int>> val(4 * N); void update(int ind,int nl,int nr,int l,int r,int v){ if(nl > r || l > nr) return; if(l <= nl && r >= nr){ if(v == 1) val[ind].insert(r); if(v == -1) val[ind].erase(val[ind].find(r)); return; } int mid = (nl + nr) / 2; update(2 * ind,nl,mid,l,r,v); update(2 * ind + 1,mid + 1,nr,l,r,v); tree[ind] = max(min(*val[2 * ind].begin(),tree[2 * ind]),min(*val[2 * ind + 1].begin(),tree[2 * ind + 1])); } int ma; int query(int ind,int nl,int nr,int l,int r){ if(nl > r || l > nr) return 0; if(l <= nl && r >= nr){ int mini = min(ma,tree[ind]); mini = min(mini,*val[ind].begin()); return mini; } ma = min(ma,*val[ind].begin()); 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; for(int i = 0;i < 4 * n;i++){ val[i].insert(N + 5); } vector<pair<int,int>> rn(m); for(int i = 0;i < m;i++){ cin >> rn[i].first >> rn[i].second; rn[i].first --; rn[i].second --; update(1,0,n - 1,rn[i].first,rn[i].second,1); } sort(rn.begin(),rn.end()); vector<Data> que(q); for(int i = 0;i < q;i++){ cin >> que[i].l >> que[i].r; que[i].l --; que[i].r --; que[i].i = i; } sort(que.begin(),que.end()); int j = 0; vector<bool> ans(q); for(int i = 0;i < q;i++){ while(j < m && rn[j].first < que[i].l){ update(1,0,n - 1,rn[j].first,rn[j].second,-1); j ++; } ma = N + 5; if(query(1,0,n - 1,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...