Submission #775786

#TimeUsernameProblemLanguageResultExecution timeMemory
775786HD1Trampoline (info1cup20_trampoline)C++14
100 / 100
977 ms89108 KiB
//we are all lost trying to be someone. #include <bits/stdc++.h> #define fastio ios_base::sync_with_stdio(0); cin.tie(0); #define sz(x) ll(x.size()) #define reve(x) reverse(x.begin(),x.end()) #define ff first #define ss second #define all(a) a.begin(), a.end() using namespace std; typedef long long ll; typedef long double ld; typedef pair<double,ll> ii; const ll MAX=(1e5+10)*2; const ll mod=1e9+7; map<ii,ll>nod; map<ll, vector<ll>> V; ll x[MAX], y[MAX]; ll spt[30][MAX]; ll up(ll a, ll b){ auto it = lower_bound( all(V[a]), b); if(it == V[a].end()) return 0; return nod[{a,*it}]; } void solve(){ ll n , m, k; cin >> n >> m >> k; for(ll i = 1; i <= k; i++){ cin >> x[i] >> y[i]; nod[ {x[i] , y[i] } ] =i; V[ x[i] ].push_back( y[i] ); } for(auto &it : V) sort( it.ss.begin(), it.ss.end()); for(ll i = 1; i <= k; i++) spt[0][i] = up(x[i]+1 , y[i]); for(ll j = 1; j < 30; j++){ for(ll i = 1; i <=k; i++){ spt[j][i] = spt[j-1][spt[j-1][i]]; } } ll x1, y1, x2, y2; ll t; cin >> t; while( t--){ cin >> x1 >> y1 >> x2 >> y2; ll dist = x2 - x1; if(x1 > x2 || y1 > y2) cout << "No\n" ; else if(dist == 0)cout << "Yes\n"; else{ ll u=up(x1,y1); dist--; for(ll i = 0; i < 30; i++){ if((dist >> i) & 1){ u = spt[i][u]; } } if(u != 0 && y[u] <= y2) cout<<"Yes\n"; else cout<<"No\n"; } } return; } int main(){ fastio; solve(); 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...