Submission #532917

#TimeUsernameProblemLanguageResultExecution timeMemory
532917Farhan_HYTrampoline (info1cup20_trampoline)C++14
0 / 100
2088 ms119708 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]; void build() { for(auto y: mp) { for(auto x: y.S) sparce[num[y.F][x]][0] = num[y.F + 1][*mp[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 start = mp[y].lower_bound(x); auto stop = rmp[yy - 1].lower_bound(-xx); if (start == mp[y].end() || stop == rmp[yy - 1].end()) { cout << "No\n"; continue; } int cur = num[y][*start]; int cury = y; int curx = *start; int j = LOG - 1; yy--; while(cury < yy) { while ((1 << j) > yy - cury) j--; cur = sparce[cur][j]; cury += (1 << j); curx = getx[cur]; if (cur == 0) { curx = inf; break; } } if (curx <= xx) 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...