#include <bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int N = 3e5+5;
struct tree{
struct node{
node *l,*r;
int sum;
node(int k) : sum(k),l(nullptr),r(nullptr) {}
node(node* l,node* r) : l(l),r(r) {
sum = max((l?l->sum:0),(r?r->sum:0));
}
};
public:
typedef node* pnode;
pnode roots[N];
node* build(int l,int r) {
if(l==r)return new node(0);
int mid = (l+r)/2;
return new node(build(l,mid),build(mid+1,r));
}
node* upd(node* cur,int l,int r,int tar,int val) {
if(l>r)return 0;
if(l==r) return new node(val);
assert(cur);
int mid = (l+r)/2;
if(tar > mid) return new node(cur->l,upd(cur->r,mid+1,r,tar,val));
else return new node(upd(cur->l,l,mid,tar,val),cur->r);
}
int qry(node*cur,int l,int r,int ll,int rr) {
if(!cur)return 0;
if(l>r||r<ll|l>rr)return 0;
if(l>=ll&&r<=rr)return cur->sum;
int mid = (l+r)/2;
return max(qry(cur->l,l,mid,ll,rr), qry(cur->r,mid+1,r,ll,rr));
}
}t;
int n,m,q,a,b;
map<int,int> times;
int main() {
cin>>n>>m>>q;
vector<pii> v(m);
vector<int> mx(n+1);
vector<pii> qv(q);
for(int i = 0;i<m;i++) {
cin>>v[i].s>>v[i].f; // r, l
}
for(int i = 0;i<q;i++)cin>>qv[i].f>>qv[i].s;
t.roots[0] = t.build(1,n);
for(int i = 0;i<m;i++) {
times[v[i].f] = i;
// cout << v[i].f << "awvdwa\n";
mx[v[i].s] = max(mx[v[i].s],v[i].f);
t.roots[i+1] = t.upd(t.roots[i],1,n,v[i].s,mx[v[i].s]);
}
for(int i = 0;i<q;i++) {
int can = 1;
int time = times[qv[i].s];
if(time ==0){
cout << "NO\n";
continue;
}
//search from .s to .f, see if max is equal to .f
int r = qv[i].s, l = qv[i].s;
// cout << l << " " << r << " " << time << "\n";
while(r < qv[i].f) {
int oldr = r;
r = t.qry(t.roots[time],1,n,l,r);
if(oldr == r) {
can = 0;
break;
}
}
if(can)cout<<"YES\n";
else cout << "NO\n";
}
}
/*
6 2 3
1 2
3 4
1 3
1 4
1 5
*/
Compilation message
curtains.cpp: In constructor 'tree::node::node(int)':
curtains.cpp:10:13: warning: 'tree::node::sum' will be initialized after [-Wreorder]
10 | int sum;
| ^~~
curtains.cpp:9:15: warning: 'tree::node* tree::node::l' [-Wreorder]
9 | node *l,*r;
| ^
curtains.cpp:11:9: warning: when initialized here [-Wreorder]
11 | node(int k) : sum(k),l(nullptr),r(nullptr) {}
| ^~~~
curtains.cpp: In member function 'int tree::qry(tree::node*, int, int, int, int)':
curtains.cpp:34:18: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
34 | if(l>r||r<ll|l>rr)return 0;
| ~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
