This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ins insert
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
#define _ << " " <<
mt19937 rng(time(0));
const int mod = 998244353,
sze = 5e5 +23,
inf = INT_MAX,
Lg = 31;
int T[sze*4];
int L[sze*4];
void upd(int l,int r,int v,int node=1,int lx=0,int rx=sze){
if(lx>r || rx<l){
return;
}
// cout<<node<<endl;
if(lx>=l && rx<=r){
// cout<<lx<<" "<<rx<<" "<<v<<endl;
T[node]=min(T[node],v);
L[node]=min(L[node],v);
return;
}
int mid = (lx+rx)/2;
upd(l,r,v,node*2,lx,mid);
upd(l,r,v,node*2 +1,mid+1,rx);
T[node]=min(max(T[node*2],T[node*2 +1]),L[node]);
}
int qry(int l,int r,int node=1,int lx=0,int rx=sze){
if(lx>r || rx<l){
return inf*2;
}
if(l<=lx && rx<=r){
return T[node] ;
}
int mid = (lx+rx)/2;
int left = qry(l,r,node*2,lx,mid);
int right = qry(l,r,node*2 +1,mid+1,rx);
if(left>inf){
return min(L[node],right);
}
if(right>inf){
return min(L[node],left);
}
return min(max(left,right),L[node]);
}
void _0x0(){
for(int i=0;i<sze*4;i++){
T[i]=inf;
L[i]=inf;
}
int n,m,q;
cin>>n>>m>>q;
vector<pair<int,int>> event[n+10];
vector<int> ans(q);
for(int i=0;i<m;i++){
int l,r;cin>>l>>r;
event[l].pb({-1,r});
}
for(int i=0;i<q;i++){
int l,r;cin>>l>>r;
event[l].pb({i,r});
}
for(int i = n;i>=1;i--){
sort(all(event[i]));
for(auto [k,v]:event[i]){
if(k==-1){
upd(i,v,v);
}
else{
int x = qry(i,v);
// cout<<i _ ":" _ v _ ".." _ x _ "::"<<endl;
ans[k]=(x<=v);
}
}
}
for(auto v:ans) cout<<(v?"YES":"NO")<<endl;
// upd(2,5,3);
// cout<<qry(2,5)<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int tt = 1;
// cin>>tt;
while(tt--){
_0x0();
}
return 0;
}
Compilation message (stderr)
curtains.cpp: In function 'void _0x0()':
curtains.cpp:76:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
76 | for(auto [k,v]:event[i]){
| ^
# | 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... |