| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1323483 | aryan | Curtains (NOI23_curtains) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int inf = 1e9;
struct Vertex{
Vertex () {}
Vertex* l;
Vertex* r;
int v;
int lz;
};
Vertex* build(int nl,int nr){
if(nl == nr){
Vertex* nv = new Vertex();
nv->v = inf;
nv->lz = inf;
return nv;
// return new Vertex(a[nl]);
}else{
int mid = (nl + nr) / 2;
Vertex* nv = new Vertex();
nv-> l = build(nl,mid);
nv-> r = build(mid + 1,nr);
nv->v = max(nv->l->v,nv->r->v);
nv->lz = inf;
return nv;
// return new Vertex(build(nl,mid,a),build(mid + 1,nr,a));
}
}
Vertex* update(Vertex* v,int nl,int nr,int &l,int &r){
if(nl > r || l > nr) return nullptr;
if(l <= nl && r >= nr){
Vertex* nv = new Vertex();
nv->l = v->l;
nv->r = v->r;
nv->v = min(r,v->v);
nv->lz = min(v->lz,r);
return nv;
}
int mid = (nl + nr) / 2;
Vertex* nv = new Vertex();
nv->lz = v->lz;
Vertex *nle = update(v->l,nl,mid,l,r);
Vertex *nre = update(v->r,mid + 1,nr,l,r);
if(nle != nullptr){
nv->l = nle;
}else{
nv->l = v->l;
}
if(nre != nullptr){
nv->r = nre;
}else{
nv->r = v->r;
}
nv->v = min(v->v,max(nv->l->v,nv->r->v));
return nv;
}
int mini = inf;
int query(Vertex* v,int nl,int nr,int &l,int &r){
if(nl > r || l > nr) return 0;
if(l <= nl && r >= nr){
return min(mini,v->v);
}
int mid = (nl + nr) / 2;
int tm = mini;
mini = min(mini,v->lz);
int a = query(v->l,nl,mid,l,r);
int b = query(v->r,mid + 1,nr,l,r);
mini = tm;
return max(a,b);
}
struct Data{
Data () {};
int l,r,i;
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;
rn[i].first --;
rn[i].second --;
}
sort(rn.begin(),rn.end());
vector<Vertex*> roots;
roots.push_back(build(0,n));
for(int i = m - 1;i >= 0;i--){
roots.push_back(update(roots[m - i - 1],0,n,rn[i].first,rn[i].second));
}
vector<Data> que(q);
for(int i = 0;i < q;i++){
// cin >> que[i].first >> que[i].second;
cin >> que[i].l >> que[i].r;
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 && rn[j].first < que[i].l){
j ++;
}
mini = inf;
if(query(roots[m - j],0,n,que[i].l,que[i].r) > que[i].r){
// cout << "NO\n";
ans[que[i].i] = false;
}else{
// cout << "YES\n";
ans[que[i].i] = true;
}
}
for(int i = 0;i < q;i++){
cout << (ans[i] ? "YES\n" : "NO\n");
}
return 0;
}