#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 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... |