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 pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
const int MAXN = 5e5+5;
int t[4*MAXN],lazy[4*MAXN];
void pushdown(int v){
lazy[2*v] = max(lazy[2*v],lazy[v]);
lazy[2*v+1] = max(lazy[2*v+1],lazy[v]);
t[2*v] = max(t[2*v],lazy[v]);
t[2*v+1] = max(t[2*v+1],lazy[v]);
lazy[v] = 0;
}
void upd(int v,int l,int r,int tl,int tr,int val){
if(l>r)return;
// cout<<v<<" "<<l<<" "<<r<<" "<<tl<<" "<<tr<<" "<<val<<'\n';
if(l == tl && r == tr){
t[v] = max(t[v],val);
lazy[v] = max(lazy[v],val);
return;
}
int tm = (tl+tr)/2;
pushdown(v);
upd(2*v,l,min(tm,r),tl,tm,val);
upd(2*v+1,max(l,tm+1),r,tm+1,tr,val);
t[v] = min(t[2*v],t[2*v+1]);
}
int query(int v,int l,int r,int tl,int tr){
if(l>r)return 1e9;
// cout<<"q "<<v<<" "<<l<<" "<<r<<" "<<tl<<" "<<tr<<" "<<t[v]<<'\n';
if(l == tl && r == tr)return t[v];
int tm = (tl+tr)/2;
pushdown(v);
return min(query(2*v,l,min(tm,r),tl,tm),query(2*v+1,max(l,tm+1),r,tm+1,tr));
}
int main()
{
owo
int n,m,q;
cin>>n>>m>>q;
vii range(n+1);
vector<vector<pii>>que(n+1);
for(int i=0;i<m;i++){
int l,r;
cin>>l>>r;
range[r].pb(l);
}
for(int i=0;i<q;i++){
int l,r;
cin>>l>>r;
que[r].pb({l,i});
}
vector<int>ans(q+1,1);
for(int r=1;r<=n;r++){
for(int l : range[r]){
upd(1,l,r,1,n,l);
//cout<<l<<" "<<r<<'\n';
}
//for(int i=1;i<=n;i++)cout<<query(1,i,i,1,n)<<" ";
//cout<<'\n';
for(pii x : que[r]){
int res = query(1,x.fi,r,1,n);
if(res < x.fi)ans[x.se] = 0;
}
}
for(int i=0;i<q;i++){
if(ans[i])cout<<"YES"<<'\n';
else cout<<"NO"<<'\n';
}
}
# | 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... |