Submission #403323

#TimeUsernameProblemLanguageResultExecution timeMemory
403323mjhmjh1104Abduction 2 (JOI17_abduction2)C++14
13 / 100
8 ms3276 KiB
#include <map> #include <tuple> #include <cstdio> #include <vector> #include <algorithm> using namespace std; int tree_a[131072], tree_b[131072]; vector<tuple<int, int, int>> tv; void interval_front(int i, int b, int e, int l, int r) { if (r < b || e < l) return; if (l <= b && e <= r) { tv.push_back({ i, b, e }); return; } int m = (b + e) / 2; interval_front(i * 2 + 1, b, m, l, r); interval_front(i * 2 + 2, m + 1, e, l, r); } void interval_back(int i, int b, int e, int l, int r) { if (r < b || e < l) return; if (l <= b && e <= r) { tv.push_back({ i, b, e }); return; } int m = (b + e) / 2; interval_back(i * 2 + 2, m + 1, e, l, r); interval_back(i * 2 + 1, b, m, l, r); } int lower_bound_left_real_a(int i, int b, int e, int v) { if (b == e) return b; int m = (b + e) / 2; if (tree_a[i * 2 + 2] > v) return lower_bound_left_real_a(i * 2 + 2, m + 1, e, v); return lower_bound_left_real_a(i * 2 + 1, b, m, v); } int lower_bound_left_real_b(int i, int b, int e, int v) { if (b == e) return b; int m = (b + e) / 2; if (tree_b[i * 2 + 2] > v) return lower_bound_left_real_b(i * 2 + 2, m + 1, e, v); return lower_bound_left_real_b(i * 2 + 1, b, m, v); } int lower_bound_right_real_a(int i, int b, int e, int v) { if (b == e) return b; int m = (b + e) / 2; if (tree_a[i * 2 + 1] > v) return lower_bound_right_real_a(i * 2 + 1, b, m, v); return lower_bound_right_real_a(i * 2 + 2, m + 1, e, v); } int lower_bound_right_real_b(int i, int b, int e, int v) { if (b == e) return b; int m = (b + e) / 2; if (tree_b[i * 2 + 1] > v) return lower_bound_right_real_b(i * 2 + 1, b, m, v); return lower_bound_right_real_b(i * 2 + 2, m + 1, e, v); } int lower_bound_left_a(int x, int v) { tv.clear(); interval_back(0, 0, 65535, 0, x); for (auto &i: tv) { auto [ a, b, c ] = i; if (tree_a[a] > v) return lower_bound_left_real_a(a, b, c, v); } return -1; } int lower_bound_left_b(int x, int v) { tv.clear(); interval_back(0, 0, 65535, 0, x); for (auto &i: tv) { auto [ a, b, c ] = i; if (tree_b[a] > v) return lower_bound_left_real_b(a, b, c, v); } return -1; } int lower_bound_right_a(int x, int v) { tv.clear(); interval_front(0, 0, 65535, x, 65535); for (auto &i: tv) { auto [ a, b, c ] = i; if (tree_a[a] > v) return lower_bound_right_real_a(a, b, c, v); } return 65536; } int lower_bound_right_b(int x, int v) { tv.clear(); interval_front(0, 0, 65535, x, 65535); for (auto &i: tv) { auto [ a, b, c ] = i; if (tree_b[a] > v) return lower_bound_right_real_b(a, b, c, v); } return 65536; } int h, w, q; int a[50006], b[50006], rt[100006]; pair<int, bool> lt[100006]; vector<pair<int, long long>> v[100006]; vector<int> compress; int main() { scanf("%d%d%d", &w, &h, &q); for (int i = 0; i < w; i++) scanf("%d", a + i); for (int i = 0; i < h; i++) scanf("%d", b + i); for (int i = 0; i < w; i++) compress.push_back(a[i]); for (int i = 0; i < h; i++) compress.push_back(b[i]); sort(compress.begin(), compress.end()); for (int i = 0; i < w; i++) a[i] = lower_bound(compress.begin(), compress.end(), a[i]) - compress.begin(); for (int i = 0; i < h; i++) b[i] = lower_bound(compress.begin(), compress.end(), b[i]) - compress.begin(); for (int i = 0; i < w; i++) lt[a[i]] = { i, false }; for (int i = 0; i < h; i++) lt[b[i]] = { i, true }; for (int i = 0; i < w; i++) tree_a[65535 + i] = a[i]; for (int i = 0; i < h; i++) tree_b[65535 + i] = b[i]; for (int i = 65534; i >= 0; i--) { tree_a[i] = max(tree_a[i * 2 + 1], tree_a[i * 2 + 2]); tree_b[i] = max(tree_b[i * 2 + 1], tree_b[i * 2 + 2]); } for (int i = 0; i < q; i++) { int s, t; scanf("%d%d", &t, &s); s--, t--; long long res = 0; for (int j = 0; j < h + w; j++) v[j].clear(), rt[j] = -1; if (s > 0) { // up int it = lower_bound_left_b(s - 1, a[t]); if (it < 0) res = max(res, (long long)s); else { v[b[it]].push_back({ t, s - it }); rt[b[it]] = lower_bound_left_a(t, b[it]); } } if (s < h - 1) { // down int it = lower_bound_right_b(s + 1, a[t]); if (it >= 65536) res = max(res, (long long)(h - 1 - s)); else { v[b[it]].push_back({ t, it - s }); rt[b[it]] = lower_bound_left_a(t, b[it]); } } for (int i = 0; i < h + w; i++) if (!v[i].empty()) { if (!lt[i].second) { int above = rt[i], bottom = lower_bound_right_b(v[i].front().first, a[lt[i].first]); if (above < 0) for (auto &j: v[i]) res = max(res, j.second + j.first); else { int tmp = lower_bound_left_a(lt[i].first, b[above]); if (!v[b[above]].empty() && rt[b[above]] != tmp) v[b[above]].clear(); long long ret = 0; for (auto &j: v[i]) ret = max(ret, j.second + (j.first - above)); v[b[above]].push_back({ lt[i].first, ret }); rt[b[above]] = tmp; } if (bottom >= 65536) for (auto &j: v[i]) res = max(res, j.second + (h - 1 - j.first)); else { int tmp = lower_bound_left_a(lt[i].first, b[bottom]); if (!v[b[bottom]].empty() && rt[b[bottom]] != tmp) v[b[bottom]].clear(); long long ret = 0; for (auto &j: v[i]) ret = max(ret, j.second + (bottom - j.first)); v[b[bottom]].push_back({ lt[i].first, ret }); rt[b[bottom]] = tmp; } } else { int left = rt[i], right = lower_bound_right_a(v[i].front().first, b[lt[i].first]); if (left < 0) for (auto &j: v[i]) res = max(res, j.second + j.first); else { int tmp = lower_bound_left_b(lt[i].first, a[left]); if (!v[a[left]].empty() && rt[a[left]] != tmp) v[a[left]].clear(); long long ret = 0; for (auto &j: v[i]) ret = max(ret, j.second + (j.first - left)); v[a[left]].push_back({ lt[i].first, ret }); rt[a[left]] = tmp; } if (right >= 65536) for (auto &j: v[i]) res = max(res, j.second + (w - 1 - j.first)); else { int tmp = lower_bound_left_b(lt[i].first, a[right]); if (!v[a[right]].empty() && rt[a[right]] != tmp) v[a[right]].clear(); long long ret = 0; for (auto &j: v[i]) ret = max(ret, j.second + (right - j.first)); v[a[right]].push_back({ lt[i].first, ret }); rt[a[right]] = tmp; } } } for (int j = 0; j < h + w; j++) v[j].clear(), rt[j] = -1; if (t > 0) { // left int it = lower_bound_left_a(t - 1, b[s]); if (it < 0) res = max(res, (long long)t); else { v[a[it]].push_back({ s, t - it }); rt[a[it]] = lower_bound_left_b(s, a[it]); } } if (t < w - 1) { // right int it = lower_bound_right_a(t + 1, b[s]); if (it >= 65536) res = max(res, (long long)(w - 1 - t)); else { v[a[it]].push_back({ s, it - t }); rt[a[it]] = lower_bound_left_b(s, a[it]); } } for (int i = 0; i < h + w; i++) if (!v[i].empty()) { if (!lt[i].second) { int above = rt[i], bottom = lower_bound_right_b(v[i].front().first, a[lt[i].first]); if (above < 0) for (auto &j: v[i]) res = max(res, j.second + j.first); else { int tmp = lower_bound_left_a(lt[i].first, b[above]); if (!v[b[above]].empty() && rt[b[above]] != tmp) v[b[above]].clear(); long long ret = 0; for (auto &j: v[i]) ret = max(ret, j.second + (j.first - above)); v[b[above]].push_back({ lt[i].first, ret }); rt[b[above]] = tmp; } if (bottom >= 65536) for (auto &j: v[i]) res = max(res, j.second + (h - 1 - j.first)); else { int tmp = lower_bound_left_a(lt[i].first, b[bottom]); if (!v[b[bottom]].empty() && rt[b[bottom]] != tmp) v[b[bottom]].clear(); long long ret = 0; for (auto &j: v[i]) ret = max(ret, j.second + (bottom - j.first)); v[b[bottom]].push_back({ lt[i].first, ret }); rt[b[bottom]] = tmp; } } else { int left = rt[i], right = lower_bound_right_a(v[i].front().first, b[lt[i].first]); if (left < 0) for (auto &j: v[i]) res = max(res, j.second + j.first); else { int tmp = lower_bound_left_b(lt[i].first, a[left]); if (!v[a[left]].empty() && rt[a[left]] != tmp) v[a[left]].clear(); long long ret = 0; for (auto &j: v[i]) ret = max(ret, j.second + (j.first - left)); v[a[left]].push_back({ lt[i].first, ret }); rt[a[left]] = tmp; } if (right >= 65536) for (auto &j: v[i]) res = max(res, j.second + (w - 1 - j.first)); else { int tmp = lower_bound_left_b(lt[i].first, a[right]); if (!v[a[right]].empty() && rt[a[right]] != tmp) v[a[right]].clear(); long long ret = 0; for (auto &j: v[i]) ret = max(ret, j.second + (right - j.first)); v[a[right]].push_back({ lt[i].first, ret }); rt[a[right]] = tmp; } } } printf("%lld\n", res); } }

Compilation message (stderr)

abduction2.cpp: In function 'int lower_bound_left_a(int, int)':
abduction2.cpp:65:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |         auto [ a, b, c ] = i;
      |              ^
abduction2.cpp: In function 'int lower_bound_left_b(int, int)':
abduction2.cpp:75:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |         auto [ a, b, c ] = i;
      |              ^
abduction2.cpp: In function 'int lower_bound_right_a(int, int)':
abduction2.cpp:85:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |         auto [ a, b, c ] = i;
      |              ^
abduction2.cpp: In function 'int lower_bound_right_b(int, int)':
abduction2.cpp:95:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |         auto [ a, b, c ] = i;
      |              ^
abduction2.cpp: In function 'int main()':
abduction2.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     scanf("%d%d%d", &w, &h, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:109:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     for (int i = 0; i < w; i++) scanf("%d", a + i);
      |                                 ~~~~~^~~~~~~~~~~~~
abduction2.cpp:110:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |     for (int i = 0; i < h; i++) scanf("%d", b + i);
      |                                 ~~~~~^~~~~~~~~~~~~
abduction2.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         scanf("%d%d", &t, &s);
      |         ~~~~~^~~~~~~~~~~~~~~~
#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...