This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int, int>
#define f first
#define s second
#define mp make_pair
int h, w, q;
int A[50000], B[50000];
int stH[16][50000];
int stW[16][50000];
int rmq(const int st[16][50000], int L, int R) {
int best = 0;
for (int i = L; i <= R; i++) {
best = max(best, st[0][i]);
}
return best;
int maxLen = 31 - __builtin_clz(R-L+1);
return max(st[maxLen][L], st[maxLen][R - (1 << maxLen)+1]);
}
map<pair<int, ii>, int> memo;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int dp(int i, int j, int d) {
auto memoIdx = mp(i, mp(j, d));
if (memo.count(memoIdx)) {
return memo[memoIdx];
}
int maxTravel;
if (d == 0) maxTravel = i;
else if (d == 1) maxTravel = w-j-1;
else if (d == 2) maxTravel = h-i-1;
else if (d == 3) maxTravel = j;
int ans = 0;
int lo = 1, hi = maxTravel+1, mid, k = 0;
while (lo < hi) {
mid = (lo + hi)/2;
int a = i + dx[d]*mid, b = j + dy[d]*mid;
if (a < 0 || a >= h || b < 0 || b >= w) {
hi = mid;
continue;
}
if (d == 0 || d == 2) {
if (rmq(stH, min(i+dx[d], a), max(i+dx[d], a)) > B[j]) {
k = mid;
hi = mid;
} else {
lo = mid + 1;
}
}
if (d == 1 || d == 3) {
if (rmq(stW, min(j+dy[d], b), max(j+dy[d], b)) > A[i]) {
k = mid;
hi = mid;
} else {
lo = mid + 1;
}
}
}
ans += k;
if (k > 0) {
int a = i + dx[d]*k, b = j + dy[d]*k;
if (a < 0 || a >= h || b < 0 || b >= w) {
assert(false);
}
if (d == 0 || d == 2) {
assert(A[a] > B[j]);
ans += max(dp(a, b, 1), dp(a, b, 3));
}
if (d == 1 || d == 3) {
assert(B[b] > A[i]);
ans += max(dp(a, b, 0), dp(a, b, 2));
}
}
return memo[memoIdx] = max(ans, maxTravel);
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(false);
cin >> h >> w >> q;
for (int i = 0; i < h; i++) cin >> A[i];
for (int i = 0; i < w; i++) cin >> B[i];
for (int i = 0; i < h; i++) {
stH[0][i] = A[i];
}
for (int len = 1; len < 16; len++) {
for (int i = 0; i <= h - (1 << len); i++) {
stH[len][i] = max(stH[len-1][i], stH[len-1][i + (1<<(len-1))]);
}
}
for (int i = 0; i < w; i++) {
stW[0][i] = B[i];
}
for (int len = 1; len < 16; len++) {
for (int i = 0; i <= w - (1 << len); i++) {
stW[len][i] = max(stW[len-1][i], stW[len-1][i + (1<<(len-1))]);
}
}
for (int i = 0; i < q; i++) {
int s, t; cin >> s >> t; --s; --t;
int best = 0;
for (int j = 0; j < 4; j++) {
best = max(best, dp(s, t, j));
}
cout << best << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |