Submission #535642

#TimeUsernameProblemLanguageResultExecution timeMemory
535642Farhan_HYTrampoline (info1cup20_trampoline)C++14
0 / 100
2101 ms230008 KiB
#include <bits/stdc++.h> #define int long long #define float double #define pb push_back #define F first #define S second #define T int t; cin >> t; while(t--) #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int inf = 8e18; const int N = 1e6 + 6; const int M = 1e3 + 3; const int LOG = 31; const int mod = 1e9 + 7; const float pi = atan(1) * 4; map<int, set<int>> tramp; map<int, set<int>> rtramp; map<pair<int, int>, int> num; map<int, int> getx; int r, c, n; int sparce[N][LOG]; void build() { for(auto y: tramp) { set<int> st = rtramp[y.F - 1]; for(auto x: y.S) { int me = num[{y.F, x}]; auto idx = st.lower_bound(-x); if (idx == st.end()) { sparce[me][0] = 0; continue; } int he = num[{y.F - 1, -*idx}]; sparce[me][0] = he; } } for(int j = 1; j < LOG; j++) { for(auto y: tramp) { for(auto x: y.S) { int me = num[{y.F, x}]; int he = sparce[me][j - 1]; sparce[me][j] = sparce[he][j - 1]; } } } } main() { IOS cin >> r >> c >> n; for(int i = 1; i <= n; i++) { int x, y; cin >> y >> x; num[{y, x}] = i; getx[num[{y, x}]] = x; tramp[y].insert(x); rtramp[y].insert(-x); } build(); T { int y, x, yy, xx; cin >> y >> x >> yy >> xx; if (y == yy) { cout << "Yes\n"; continue; } yy--; auto it = rtramp[yy].lower_bound(-xx); if (it == rtramp[yy].end()) { cout << "No\n"; continue; } xx = -*it; it = tramp[y].lower_bound(x); if (it == tramp[y].end()) { cout << "No\n"; continue; } x = *it; int dist = yy - y; int cnt = 0; while(dist) { while(dist && (dist & 1) == 0) dist = (dist >> 1), cnt++; int me = num[{yy, xx}]; int he = sparce[me][cnt]; xx = getx[he]; yy += (1 << cnt); dist = dist >> 1; cnt++; } if(xx >= x) cout << "Yes\n"; else cout << "No\n"; } } /* 4 5 2 2 2 3 4 3 2 1 4 5 1 2 1 4 2 3 4 4 */

Compilation message (stderr)

trampoline.cpp:57:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 | main()
      | ^~~~
#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...