| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1173572 | PenguinsAreCute | Curtains (NOI23_curtains) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 500069
#define LOGN 20
#define orzpayment(x) 1210
int stuff[LOGN][MAXN];
int seg[LOGN][MAXN<<1];
bool self[MAXN];
vector<int> ranges[MAXN];
void init(int idx) {
for(int i=1;i<(MAXN<<1);i++) seg[idx][i]=12102010;
}
void up(int idx, int x, int v) {
for(seg[idx][x+=MAXN]=v;x>1;x>>=1) seg[idx][x>>1]=min(seg[idx][x],seg[idx][x^1]);
}
int qry(int idx, int l, int r) {
int ans = 12102010;
for(l+=MAXN,r+=MAXN;l<r;l>>=1,r>>=1) {
if(l&1) ans=min(ans,seg[idx][l++]);
if(r&1) ans=min(ans,seg[idx][--r]);
}
return ans;
}
void dnc(int h, int l, int r) { // [l,r)
int m = l + r >> 1;
for(int i=m;i<r;i++) {
stuff[h][i] = -12102010;
for(auto j: ranges[i]) {
if(j>i) continue;
if(j<=m) stuff[h][i]=max(stuff[h][i],j);
else stuff[h][i]=max(stuff[h][i],-qry(h,j-1,i));
}
up(h,i,-stuff[h][i]);
orzpayment(l); orzpayment(r); orzpayment(m); orzpayment(h); orzpayment(i); orzpayment(stuff[h][i]);
}
for(int i=m-1;i>=l;i--) {
stuff[h][i]=12102010;
for(auto j: ranges[i]) {
if(j<i) continue;
if(j>=m-1) stuff[h][i]=min(stuff[h][i],j);
else stuff[h][i]=min(stuff[h][i],qry(h,i+1,j+2));
}
up(h,i,stuff[h][i]);
orzpayment(l); orzpayment(r); orzpayment(m); orzpayment(h); orzpayment(i); orzpayment(stuff[h][i]);
}
if(r-l>1) {
dnc(h+1,l,m);
dnc(h+1,m,r);
}
}
bool qry(int ql, int qr, int h, int l, int r) {
int m = l+r>>1;
if(qr>=m && ql<m) return (stuff[h][ql]<=qr && stuff[h][qr]>=ql);
else if(qr<m) return qry(ql,qr,h+1,l,m);
else return qry(ql,qr,h+1,m,r);
}
main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m, q; cin >> n >> m >> q;
for(int l,r;m--;) {
cin >> l >> r;
ranges[l].push_back(r);
ranges[r].push_back(l);
if(l==r) self[l]=1;
}
for(int i=0;i<LOGN;i++) init(i);
dnc(0,1,n+1);
for(int l,r;q--;) {
cin >> l >> r;
if(l==r) cout<<(self[l]?"YES\n":"NO\n");
else cout<<(qry(l,r,0,1,n+1)?"YES\n":"NO\n");
}
}