Submission #387586

#TimeUsernameProblemLanguageResultExecution timeMemory
387586casperwangTrampoline (info1cup20_trampoline)C++14
100 / 100
1152 ms54204 KiB
#include <bits/stdc++.h> #define pb emplace_back #define All(x) x.begin(), x.end() #define pii pair<int,int> #define ff first #define ss second #define y1 y_1 using namespace std; #define debug(args...) kout("[ " + string(#args) + " ]", args) void kout() { cerr << endl; } template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); } template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; } const int MAXN = 200000; const int L = 30; int N, R, C, T; pii pts[MAXN+1]; int x1, y1, x2, y2; map <int, set<pii>> arr; int anc[MAXN+1][L]; void build() { for (int i = 1; i <= N; i++) { auto [x, y] = pts[i]; arr[x].insert(pii(y, i)); } for (int i = 1; i <= N; i++) { auto [x, y] = pts[i]; if (!arr.count(x-1)) continue; auto it = arr[x-1].upper_bound(pii(y, N+1)); if (it != arr[x-1].begin()) { anc[i][0] = prev(it)->ss; } } for (int i = 1; i < L; i++) { for (int j = 1; j <= N; j++) { anc[j][i] = anc[anc[j][i-1]][i-1]; } } } bool solve(int x1, int y1, int x2, int y2) { if (x1 == x2 && y1 <= y2) return true; if (y1 > y2 || x1 > x2) return false; if (!arr.count(x2-1)) return false; auto it = arr[x2-1].upper_bound(pii(y2, N+1)); if (it == arr[x2-1].begin()) return false; int now = prev(it)->ss; int K = x2 - x1 - 1; for (int i = 1; i <= K; i *= 2) { if (i & K) now = anc[now][__lg(i)]; } return now && pts[now].ss >= y1; } signed main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> R >> C >> N; for (int i = 1; i <= N; i++) { auto &[x, y] = pts[i]; cin >> x >> y; } build(); cin >> T; for (int i = 1; i <= T; i++) { cin >> x1 >> y1 >> x2 >> y2; cout << (solve(x1, y1, x2, y2) ? "Yes" : "No") << '\n'; } }

Compilation message (stderr)

trampoline.cpp: In function 'void build()':
trampoline.cpp:24:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |   auto [x, y] = pts[i];
      |        ^
trampoline.cpp:28:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |   auto [x, y] = pts[i];
      |        ^
trampoline.cpp: In function 'int main()':
trampoline.cpp:60:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |   auto &[x, y] = pts[i];
      |         ^
#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...