제출 #1318494

#제출 시각아이디문제언어결과실행 시간메모리
1318494Ghulam_JunaidTrampoline (info1cup20_trampoline)C++20
11 / 100
2101 ms355040 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10, SQ = 450; int n, m, g, q; int par[N][SQ]; vector<pair<int, int>> vec; int main(){ cin >> n >> m >> g; for (int i = 0; i < g; i ++){ int x, y; cin >> x >> y; vec.push_back({x, y}); } sort(vec.begin(), vec.end()); for (int i = 0; i < g; i ++){ auto [x, y] = vec[i]; x++; par[i][0] = i; int lb = lower_bound(vec.begin(), vec.end(), (pair<int, int>){x, y}) - vec.begin(); if (lb != vec.size() and vec[lb].first == x) par[i][0] = lb; } for (int i = g - 1; i >= 0; i--) for (int j = 1; j < SQ; j ++) par[i][j] = par[par[i][j - 1]][j - 1]; cin >> q; while (q--){ int sx, sy, ex, ey; cin >> sx >> sy >> ex >> ey; int f = 0; int cur = -1; while (sx < ex){ if (f == 1){ if (par[cur][SQ - 1] == cur) break; if (vec[par[cur][SQ - 1]].first < ex){ cur = par[cur][SQ - 1]; } else{ cur = par[cur][max(0, ex - sx - 2)]; f = 2; } sx = vec[cur].first + 1, sy = vec[cur].second; continue; } if (f==0) f = 1; int lb = lower_bound(vec.begin(), vec.end(), (pair<int, int>){sx, sy}) - vec.begin(); if (lb != vec.size() and vec[lb].first == sx) sy = vec[lb].second; else break; cur = lb; sx++; } if (sx == ex and sy <= ey) cout << "Yes\n"; else 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...