Submission #533052

#TimeUsernameProblemLanguageResultExecution timeMemory
533052Farhan_HYTrampoline (info1cup20_trampoline)C++14
0 / 100
2079 ms118096 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>> mp; map<int, set<int>> rmp; map<int, map<int, int>> num; map<int, int> getx; int n, c, r; int sparce[N][LOG + 1]; void build() { for(auto y: mp) { for(auto x: y.S) sparce[num[y.F][x]][0] = num[y.F - 1][-*rmp[y.F - 1].lower_bound(-x)]; } for(int j = 1; j <= LOG; j++) { for(auto y: mp) { for(auto x: y.S) { int me = num[y.F][x]; int xx = sparce[me][j - 1]; sparce[me][j] = sparce[xx][j - 1]; } } } } main() { IOS cin >> r >> c >> n; for(int i = 1; i <= n; i++) { int x, y; cin >> y >> x; getx[i] = x; mp[y].insert(x); rmp[y].insert(-x); num[y][x] = i; } build(); T { int y, x, yy, xx; cin >> y >> x >> yy >> xx; if (y == yy) { cout << "Yes\n"; continue; } auto stop = rmp[yy - 1].lower_bound(-xx); auto start = mp[y].lower_bound(x); if (stop == rmp[yy - 1].end() || start == mp[y].end()) { cout << "No\n"; continue; } x = *start; xx = -*stop; yy--; int me = num[yy][xx]; int j = LOG; while(yy > y) { while((1ll << j) > yy - y) j--; yy -= (1ll << j); xx = sparce[me][j]; xx = getx[xx]; me = num[yy][xx]; if (me == 0) { y = -inf; x = -inf; break; } } if (xx >= x) cout << "Yes\n"; else cout << "No\n"; } }

Compilation message (stderr)

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