Submission #892934

#TimeUsernameProblemLanguageResultExecution timeMemory
892934XiaoyangTrampoline (info1cup20_trampoline)C++17
100 / 100
1010 ms84816 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second #define pii pair<int,int> #define pll pair<long long,long long> #define pb push_back #define debug(x) cout<<#x<<"="<<x<<endl #define pq priority_queue #define inf 1ll<<60 #define rep(i,a,b) for (ll i=a;i<(b);i++) #define MP make_pair #define SZ(x) (int(x.size())) #define mod 1000000007 #define ALL(x) x.begin(),x.end() #define endl "\n" void inc(ll &a,ll b) {a=(a+b)%mod;} void dec(ll &a,ll b) {a=(a-b+mod)%mod;} int prod(ll a,ll b) {return ll(a)*ll(b)%mod;} int lowbit(ll x) {return x&(-x);} ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;} const ll lg=22; const ll maxn=2e5+5; ll twok[maxn][lg]; ll row[maxn],col[maxn]; map<ll,vector<ll>>mp; map<pll,ll>id; int main() { ios::sync_with_stdio(0); cin.tie(0); ll r,c,n;cin>>r>>c>>n; rep(i,1,n+1){ cin>>row[i]>>col[i]; mp[row[i]].pb(col[i]); id[MP(row[i],col[i])]=i; } for(auto x:mp){ sort(ALL(mp[x.fi])); //for(auto y:mp[x.fi])cout<<y<<" "; //cout<<endl; } rep(i,1,n+1){ auto it=lower_bound(ALL(mp[row[i]+1]),col[i]); if(it==mp[row[i]+1].end())continue; twok[i][0]=id[MP(row[i]+1,*it)]; } rep(j,1,lg){ rep(i,1,n+1){ twok[i][j]=twok[twok[i][j-1]][j-1]; } } /* rep(i,1,n+1){ rep(j,0,lg){ cout<<twok[i][j]<<" "; } cout<<endl; } */ ll t;cin>>t; while(t--){ ll x,y,xx,yy; cin>>x>>y>>xx>>yy; ll diff=xx-x; if(xx<x or yy<y)cout<<"No"<<endl; else if(diff==0)cout<<"Yes"<<endl; else{ ll u; auto it=lower_bound(ALL(mp[x]),y); if(it==mp[x].end())u=0; else u=id[MP(x,*it)]; diff--; rep(i,0,lg){ if(diff&(1<<i)){ u=twok[u][i]; } } if(u==0 or col[u]>yy)cout<<"No"<<endl; else cout<<"Yes"<<endl; } } return 0; }
#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...