#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define all(aa) aa.begin(), aa.end()
struct SegmentTree{
int N;
vector<int> st, lazy, arr;
SegmentTree(int N, int val=0): N(N), arr(N, val), st(4*N), lazy(4*N){
build(1, 0, N-1);
}
int build(int n, int s, int e){
if(s==e) return st[n]=arr[s];
int mid=(s+e)/2;
return st[n]=build(n*2, s, mid)+build(n*2+1, mid+1, e);
}
void push(int n){
st[n*2]+=lazy[n]; st[n*2+1]+=lazy[n];
lazy[n*2]+=lazy[n]; lazy[n*2+1]+=lazy[n];
lazy[n]=0;
}
void update(int n, int s, int e, int l, int r, int val){
if(s>=l && e<=r){
lazy[n]+=val;
st[n]+=val;
return ;
}
push(n);
int mid=(s+e)/2;
if(mid>=l) update(n*2, s, mid, l, r, val);
if(mid<r) update(n*2+1, mid+1, e, l, r, val);
st[n]=min(st[n*2], st[n*2+1]);
}
int query(int n, int s, int e, int l, int r){
if(s>=l && e<=r) return st[n];
push(n);
int mid=(s+e)/2, ans=INT_MAX;
if(mid>=l) ans=min(ans, query(n*2, s, mid, l, r));
if(mid<r) ans=min(ans, query(n*2+1, mid+1, e, l, r));
return ans;
}
int query(int l, int r){
return query(1, 0, N-1, l, r);
}
void update(int l, int r, int val){
return update(1, 0, N-1, l, r, val);
}
};
const int SQRT=700;
int main(){
int n, m, q;
cin>>n>>m>>q;
vector<set<int>> beg(n), end(n);
SegmentTree st(n);
for(int i=0; i<m; i++){
int a, b;
cin>>a>>b;
a--; b--;
beg[a].insert(b);
end[b].insert(a);
st.update(a, b, 1);
}
priority_queue<array<int, 4>, vector<array<int, 4>>, greater<array<int, 4>>> mo;
for(int i=0; i<q; i++){
int l, r;
cin>>l>>r;
l--; r--;
mo.push({l/SQRT, r, l, i});
}
int cur_l=0, cur_r=n-1;
vector<bool> ans(q);
while(mo.size()){
auto [block, r, l, ind]=mo.top();
mo.pop();
for(int i=cur_l; i<l; i++){
auto it=upper_bound(all(beg[i]), cur_r);
if(it!=beg[i].begin()){
int u=*prev(it);
st.update(i, u, -1);
}
}
for(int i=cur_r; i>r; i--){
auto it=lower_bound(all(end[i]), cur_l);
if(it!=end[i].end()){
int u=*it;
st.update(u, i, -1);
}
}
for(int i=cur_l; i>=l; i--){
auto it=upper_bound(all(beg[i]), r);
if(it!=beg[i].begin()){
int u=*prev(it);
st.update(i, u, 1);
}
}
for(int i=cur_r; i<=r; i++){
auto it=lower_bound(all(end[i]), l);
if(it!=end[i].end()){
int u=*it;
st.update(u, i, 1);
}
}
ans[ind]=(st.query(l, r)==0);
cur_l=l; cur_r=r;
}
for(int i=0; i<q; i++) cout<<(ans[i] ? "NO":"YES")<<endl;
}
Compilation message
curtains.cpp: In constructor 'SegmentTree::SegmentTree(int, int)':
curtains.cpp:10:24: warning: 'SegmentTree::arr' will be initialized after [-Wreorder]
10 | vector<int> st, lazy, arr;
| ^~~
curtains.cpp:10:14: warning: 'std::vector<int> SegmentTree::st' [-Wreorder]
10 | vector<int> st, lazy, arr;
| ^~
curtains.cpp:12:2: warning: when initialized here [-Wreorder]
12 | SegmentTree(int N, int val=0): N(N), arr(N, val), st(4*N), lazy(4*N){
| ^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
