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 forn(i, a, b) for(int i=a; i<=b; ++i)
#define ford(i, a, b) for(int i=a; i>=b; --i)
#define repn(i, a, b) for(int i=a; i <b; ++i)
#define repd(i, a, b) for(int i=(int)a-1; i>=b; --i)
const int maxLog = 19;
const int maxN = 5e4 +10;
int H, W, Q;
int A[maxN], B[maxN];
int pw[maxLog];
int col[maxN][maxLog], row[maxN][maxLog];
map< tuple<int, int, int>, int > dp;
int max(int a, int b, int c, int d) {
return max( max(a, b), max(c, d) );
}
int DFS(int cur_x, int cur_y, int dir) {
tuple<int, int, int> cur_state = {cur_x, cur_y, dir};
if (dp.count(cur_state)) return dp[cur_state];
int &ans = dp[cur_state];
if (dir == 0 || dir == 1) {
int sign = (dir == 0 ? -1 : 1);
int nxt = -1;
int tmp = cur_x;
ford(i, 16, 0) {
nxt = cur_x + pw[i] * sign - sign;
if (nxt < 1 || nxt > H) continue;
if ( (sign == 1 ? row[cur_x][i] : row[nxt][i]) > B[cur_y] ) continue;
cur_x = nxt + sign;
}
if (cur_x < 1 || cur_x > H) {
cur_x -= sign;
return ans = abs(cur_x - tmp);
}
return ans = abs(cur_x - tmp) + max( DFS(cur_x, cur_y, 2), DFS(cur_x, cur_y, 3) );
}
int sign = (dir == 2 ? -1 : 1);
int nxt = -1;
int tmp = cur_y;
ford(i, 16, 0) {
nxt = cur_y + pw[i] * sign - sign;
if (nxt < 1 || nxt > W) continue;
if ( (sign == 1 ? col[cur_y][i] : col[nxt][i]) > A[cur_x] ) continue;
cur_y = nxt + sign;
}
if (cur_y < 1 || cur_y > W) {
cur_y -= sign;
return ans = abs(cur_y - tmp);
}
return ans = abs(cur_y - tmp) + max( DFS(cur_x, cur_y, 0), DFS(cur_x, cur_y, 1) );
}
int main() {
ios::sync_with_stdio(0);
pw[0] = 1;
forn(i, 1, 17) pw[i] = pw[i-1] * 2;
cin >> H >> W >> Q;
forn(i, 1, H) cin >> A[i];
forn(i, 1, W) cin >> B[i];
forn(i, 1, H) row[i][0] = A[i];
forn(i, 1, W) col[i][0] = B[i];
forn(lg, 1, 16) forn(i, 1, H-pw[lg]+1)
row[i][lg] = max(row[i][lg-1], row[i+pw[lg-1]][lg-1]);
forn(lg, 1, 16) forn(i, 1, W-pw[lg]+1)
col[i][lg] = max(col[i][lg-1], col[i+pw[lg-1]][lg-1]);
for(int S, T; Q; Q--) {
cin >> S >> T;
int ans = 0;
if (S < H) ans = max(ans, DFS(S+1, T, 1) + 1);
if (S > 1) ans = max(ans, DFS(S-1, T, 0) + 1);
if (T < W) ans = max(ans, DFS(S, T+1, 3) + 1);
if (T > 1) ans = max(ans, DFS(S, T-1, 2) + 1);
cout << ans << '\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... |