Submission #699093

#TimeUsernameProblemLanguageResultExecution timeMemory
699093tengiz05Abduction 2 (JOI17_abduction2)C++17
44 / 100
99 ms20108 KiB
#include <bits/stdc++.h> using i64 = long long; constexpr int Log = 16; constexpr int N = 50000; int am[Log][N], bm[Log][N]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m, q; std::cin >> n >> m >> q; std::vector<int> a(n), b(m); for (int i = 0; i < n; i++) { std::cin >> a[i]; } for (int i = 0; i < m; i++) { std::cin >> b[i]; } for (int i = 0; i < n; i++) am[0][i] = a[i]; for (int j = 0; (1 << (j + 1)) <= n; j++) for (int i = 0; i + (1 << (j + 1)) <= n; i++) am[j + 1][i] = std::max(am[j][i], am[j][i + (1 << j)]); for (int i = 0; i < m; i++) bm[0][i] = b[i]; for (int j = 0; (1 << (j + 1)) <= m; j++) for (int i = 0; i + (1 << (j + 1)) <= m; i++) bm[j + 1][i] = std::max(bm[j][i], bm[j][i + (1 << j)]); std::unordered_map<i64, i64> dp; std::function<int(int, int, int)> calc = [&](int x, int y, int t) { i64 state = x * 1LL * m + y + t * (1LL << 60); if (dp.count(state)) return dp[state]; int res = 0; if (t == 0) { int j = y + 1; for (int k = Log - 1; k >= 0; k--) if (j + (1 << k) <= m && bm[k][j] <= a[x]) j += 1 << k; if (j == m) res = std::max(res, m - 1 - y); else res = std::max(res, j - y + calc(x, j, !t)); j = y; for (int k = Log - 1; k >= 0; k--) if (j - (1 << k) >= 0 && bm[k][j - (1 << k)] <= a[x]) j -= 1 << k; j--; if (j == -1) res = std::max(res, y); else res = std::max(res, y - j + calc(x, j, !t)); } else { int i = x + 1; for (int k = Log - 1; k >= 0; k--) if (i + (1 << k) <= n && am[k][i] <= b[y]) i += 1 << k; if (i == n) res = std::max(res, n - 1 - x); else res = std::max(res, i - x + calc(i, y, !t)); i = x; for (int k = Log - 1; k >= 0; k--) if (i - (1 << k) >= 0 && am[k][i - (1 << k)] <= b[y]) i -= 1 << k; i--; if (i == -1) res = std::max(res, x); else res = std::max(res, x - i + calc(i, y, !t)); } return dp[state] = res; }; while (q--) { int s, t; std::cin >> s >> t; s--; t--; std::cout << std::max(calc(s, t, 0), calc(s, t, 1)) << "\n"; } return 0; }
#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...