Submission #974364

#TimeUsernameProblemLanguageResultExecution timeMemory
974364CSQ31Curtains (NOI23_curtains)C++17
9 / 100
67 ms17748 KiB
#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(n+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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...