Submission #339684

#TimeUsernameProblemLanguageResultExecution timeMemory
339684wwddTrampoline (info1cup20_trampoline)C++14
0 / 100
2095 ms7648 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pl; const int MN = 200200; const int LOG = 20; ll nx[MN][LOG]; struct Q { ll id; pl st,ed; bool operator< (const Q& other) { return st.second < other.st.second; } }; vector<Q> qu; vector<pl> tr; map<ll,ll> mu; int main() { ios::sync_with_stdio(0);cin.tie(0); ll mr,mc; cin >> mr >> mc; ll n,N; cin >> n; for(int i=0;i<n;i++) { ll a,b; cin >> a >> b; tr.emplace_back(a,b); } sort(tr.begin(),tr.end(),[&](const pl& a, const pl& b){ if(a.second > b.second) {return true;} return a.first > b.first; }); cin >> N; vector<ll> ans(N,0); for(int i=0;i<N;i++) { ll sr,sc,tr,tc; cin >> sr >> sc >> tr >> tc; qu.push_back({i,{sr,sc},{tr,tc}}); } ll trp = 0; sort(qu.begin(),qu.end()); for(int i=N-1;i>=0;i--) { Q q = qu[i]; while(trp < tr.size() && tr[trp].second >= q.st.second) { ll r = tr[trp].first; mu[r] = trp; if(mu.count(r+1)) { nx[trp][0] = mu[r+1]; } else { nx[trp][0] = trp; } for(int i=1;i<LOG;i++) { nx[trp][i] = nx[nx[trp][i-1]][i-1]; } trp++; } ll idx = q.id; if(q.st.first == q.ed.first) { if(q.st.second <= q.ed.second) { ans[idx] = 1; } else { ans[idx] = 0; } } else if(!mu.count(q.st.first)) { ans[idx] = 0; } else { ll no = mu[q.st.first]; ll dif = q.ed.first-q.st.first-1; if(dif < 0) {ans[idx] = 0;} else { for(int i=LOG-1;i>=0;i--) { if(dif&(1<<i)) { no = nx[no][i]; } } } if(tr[no].first+1 == q.ed.first && tr[no].second <= q.ed.second) { ans[idx] = 1; } else { ans[idx] = 0; } } } for(int i=0;i<N;i++) { cout << (ans[i]?"Yes":"No") << '\n'; } }

Compilation message (stderr)

trampoline.cpp: In function 'int main()':
trampoline.cpp:44:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   while(trp < tr.size() && tr[trp].second >= q.st.second) {
      |         ~~~~^~~~~~~~~~~
#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...