Submission #807607

#TimeUsernameProblemLanguageResultExecution timeMemory
807607SorahISATrampoline (info1cup20_trampoline)C++17
100 / 100
591 ms56492 KiB
#ifndef SorahISA #define SorahISA #include SorahISA __FILE__ SorahISA const int lgmx = 18; void solve() { int R, C, N; cin >> R >> C >> N; vector<pii> green_vec(N); map<int, set<pii>> green; for (int i = 0, r, c; i < N; ++i) cin >> r >> c, green_vec[i] = {r, c}, green[r].ee(c, i); vector anc(lgmx, vector<int>(N+1, N)); for (const auto &[r, st_c] : green) { if (!green.count(r+1)) continue; const set<pii> &nxt = green[r+1]; for (const auto &[c, id] : st_c) { const auto it = nxt.lower_bound({c, 0}); if (it == end(nxt)) break; anc[0][id] = it->second; } } for (int lay = 1; lay < lgmx; ++lay) { for (int i = 0; i < N; ++i) anc[lay][i] = anc[lay-1][anc[lay-1][i]]; } int T; cin >> T; for (int q = 1; q <= T; ++q) { int sx, sy, ex, ey; cin >> sx >> sy >> ex >> ey; if (sx > ex or (sx == ex and sy > ey)) {cout << "No" << "\n"; continue;} if (sx == ex) {cout << "Yes" << "\n"; continue;} if (!green.count(sx) or green[sx].lower_bound({sy, 0}) == end(green[sx])) {cout << "No" << "\n"; continue;} int dif = ex - sx - 1, now = green[sx].lower_bound({sy, 0})->second; for (int lay = lgmx-1; lay >= 0; --lay) { if (dif >> lay & 1) now = anc[lay][now]; } if (now < N and green_vec[now].second <= ey) cout << "Yes" << "\n"; else cout << "No" << "\n"; } } int32_t main() { fastIO(); int t = 1; // cin >> t; for (int _ = 1; _ <= t; ++_) { solve(); } return 0; } #else #ifdef local #define _GLIBCXX_DEBUG 1 #endif #pragma GCC optimize("Ofast", "unroll-loops") #include <bits/stdc++.h> using namespace std; // #define int int64_t // #define double __float80 using pii = pair<int, int>; template <typename T> using Prior = std::priority_queue<T>; template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>; // #define X first // #define Y second #define eb emplace_back #define ef emplace_front #define ee emplace #define pb pop_back #define pf pop_front #define ALL(x) begin(x), end(x) #define RALL(x) rbegin(x), rend(x) #define SZ(x) ((int)(x).size()) #ifdef local #define fastIO() void() #define debug(...) \ fprintf(stderr, "%sAt [%s], line %d: (%s) = ", "\u001b[33m", __FUNCTION__, __LINE__, #__VA_ARGS__), \ _do(__VA_ARGS__), fprintf(stderr, "%s", "\u001b[0m") template <typename T> void _do(T &&_t) {cerr << _t << "\n";} template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);} #else #define fastIO() ios_base::sync_with_stdio(0), cin.tie(0) #define debug(...) void() #endif mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;} template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;} #endif
#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...