#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 time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |