#include "bits/stdc++.h"
using namespace std;
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
using ll = long long;
int a[50000], b[50000];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int ndir[] = {1, 0, 3, 2};
int h, w, q;
map<tuple<int, int , int>, ll> m;
int jmph[50005][20];
int jmpw[50005][20];
bool in(int x, int y) {
return (1 <= x && x <= h && 1 <= y && y <= w);
}
ll dp(int x, int y, int dir) {
if (m.count({x, y, dir})) return m[{x, y, dir}];
ll &ans = m[{x, y, dir}];
switch(dir) {
case 0:
{
int loc = x;
for (int j = 19; j >= 0; j--) {
int nxt = (1 << j) - 1;
if (loc + nxt > h) continue;
if (jmph[loc][j] > b[y]) continue;
loc += (nxt + 1);
}
if (loc > h) return ans = abs(loc - 1 - x);
return ans = max(dp(loc, y, 2), dp(loc, y, 3)) + (loc - x);
break;
}
case 1:
{
int loc = x;
for (int j = 19; j >= 0; j--) {
int nxt = (1 << j) - 1;
if (loc - nxt < 1) continue;
if (jmph[loc - nxt][j] > b[y]) continue;
loc -= (nxt + 1);
}
if (loc < 1) return ans = abs(x - loc - 1);
return ans = max(dp(loc, y, 2), dp(loc, y, 3)) + (x - loc);
break;
}
case 2:
{
int loc = y;
for (int j = 19; j >= 0; j--) {
int nxt = (1 << j) - 1;
if (loc + nxt > w) continue;
if (jmpw[loc][j] > a[x]) continue;
loc += (nxt + 1);
}
if (loc > w) return ans = abs(loc - 1 - y);
return ans = max(dp(x, loc, 0), dp(x, loc, 1)) + (loc - y);
break;
}
case 3:
{
int loc = y;
for (int j = 19; j >= 0; j--) {
int nxt = (1 << j) - 1;
if (loc - nxt < 1) continue;
if (jmpw[loc - nxt][j] > a[x]) continue;
loc -= (nxt + 1);
}
if (loc < 1) return ans = abs(y - loc - 1);
return ans = max(dp(x, loc, 0), dp(x, loc, 1)) + (y - loc);
break;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("", "r", stdin);
// freopen("", "w", stdout);
cin >> h >> w >> q;
for (int i = 1; i <= h; i++) {
cin >> a[i];
jmph[i][0] = a[i];
}
for (int i = 1; i <= w; i++) {
cin >> b[i];
jmpw[i][0] = b[i];
}
for (int i = 1; i <= h; i++) {
for (int j = 1; j < 20; j++) {
if (i + (1 << (j-1)) > h) break;
jmph[i][j] = max(jmph[i][j-1], jmph[i + (1 << (j-1))][j-1]);
}
}
for (int i = 1; i <= w; i++) {
for (int j = 1; j < 20; j++) {
if (i + (1 << j) - 1 > w) break;
jmpw[i][j] = max(jmpw[i][j-1], jmpw[i + (1 << j) - 1][j-1]);
}
}
while (q--) {
int s, t; cin >> s >> t;
ll longest = 0;
for (int i = 0; i < 4; i++) {
int nx = s + dx[i], ny = t + dy[i];
if (in(nx, ny)) {
longest = max(longest, dp(nx, ny, i) + 1);
}
}
cout << longest << "\n";
}
// cout << longest;
}
Compilation message
abduction2.cpp: In function 'll dp(int, int, int)':
abduction2.cpp:107:1: warning: control reaches end of non-void function [-Wreturn-type]
107 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
