Submission #675203

#TimeUsernameProblemLanguageResultExecution timeMemory
675203vjudge1Trampoline (info1cup20_trampoline)C++17
100 / 100
664 ms39356 KiB
#include<bits/stdc++.h> using namespace std; #define f first #define s second typedef long long ll; typedef long double ld; typedef pair<ll, ll> pt; int r, c, n, t; const int maxn = 2e5+5; const ll inf = 1e9+5; map<int, vector<pair<int, int>>> mp; int dd[maxn]; int sp[20][maxn]; void build(){ for(int i = 1; i < 20; i++){ for(int j = 1; j <= n; j++){ sp[i][j] = sp[i-1][sp[i-1][j]]; } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> r >> c >> n; for(int i = 1; i <= n; i++){ int a, b; cin >> a >> b; mp[a].push_back({b, i}); dd[i]=b; } for(auto it = mp.begin(); it != mp.end(); it++){ sort(it->s.begin(), it->s.end()); } for(auto v: mp){ for(auto x: v.s){ int pos = lower_bound(mp[v.f+1].begin(), mp[v.f+1].end(), make_pair(x.f, 0))-mp[v.f+1].begin(); if(pos < mp[v.f+1].size())sp[0][x.s] = mp[v.f+1][pos].s; } } build(); cin >> t; while(t--){ int xs, ys, xt, yt; cin >> xs >> ys >> xt >> yt; if(ys > yt || xs > xt || xt - xs > n){ cout << "No\n"; continue; } if(xs == xt){ cout << "Yes\n"; continue; } int pos = lower_bound(mp[xs].begin(), mp[xs].end(), make_pair(ys, 0))-mp[xs].begin(); if(pos == mp[xs].size())cout << "No\n"; else{ int crr = mp[xs][pos].s; for(int i = 0; i < 20; i++){ if((1<<i)&(xt-xs-1))crr = sp[i][crr]; } if(crr && dd[crr] <= yt)cout << "Yes\n"; else cout << "No\n"; } } }

Compilation message (stderr)

trampoline.cpp: In function 'int main()':
trampoline.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             if(pos < mp[v.f+1].size())sp[0][x.s] = mp[v.f+1][pos].s;
      |                ~~~~^~~~~~~~~~~~~~~~~~
trampoline.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         if(pos == mp[xs].size())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...