#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF ((int) 1e9)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 50111
#define logn 18
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
int segd[maxn][logn], segu[maxn][logn], segl[maxn][logn], segr[maxn][logn];
int a[maxn], b[maxn];
int h, w, q;
map<vector<int>, int> dp;
int findPos(int x, int val, int n, int sign, int arr[maxn][logn]){
int cur = x;
for(int i = logn - 1; i >= 0; i--){
int pos = cur + sign * ((1 << i) - 1);
if(cur < 0 || cur >= n)
break;
if(arr[cur][i] < val)
cur = pos;
}
if(cur >= n)
return n;
if(cur < 0)
return -1;
if(arr[cur][0] < val)
cur += sign;
return cur;
}
int f(int x, int y, int dir){
if(dp.count({x, y, dir}))
return dp[{x, y, dir}];
// cout << x << " " << y << " " << dir << endl;
int cur = 0;
if(dir == 0){ // left
int pos = findPos(y - 1, a[x], w, -1, segl);
int dist = abs(pos - y);
if(pos < 0)
return dist - 1;
cur = max(cur, f(x, pos, 2) + dist);
cur = max(cur, f(x, pos, 3) + dist);
}
if(dir == 1){ // right
int pos = findPos(y + 1, a[x], w, 1, segr);
int dist = abs(pos - y);
if(pos == w)
return dist - 1;
cur = max(cur, f(x, pos, 2) + dist);
cur = max(cur, f(x, pos, 3) + dist);
}
if(dir == 2){ // down
int pos = findPos(x + 1, b[y], h, 1, segd);
int dist = abs(pos - x);
if(pos == h)
return dist - 1;
cur = max(cur, f(pos, y, 0) + dist);
cur = max(cur, f(pos, y, 1) + dist);
}
if(dir == 3){ // up
int pos = findPos(x - 1, b[y], h, -1, segu);
int dist = abs(pos - x);
if(pos < 0)
return dist - 1;
cur = max(cur, f(pos, y, 0) + dist);
cur = max(cur, f(pos, y, 1) + dist);
}
dp[{x, y, dir}] = cur;
return cur;
}
void precalc(){
for(int i = 0; i < h; i++)
segu[i][0] = segd[i][0] = a[i];
for(int j = 1; j < logn; j++){
for(int i = 0; i < h; i++){
segd[i][j] = segd[i][j - 1];
int pos = i + (1 << (j - 1));
if(pos < h)
segd[i][j] = max(segd[i][j], segd[pos][j - 1]);
segu[i][j] = segu[i][j - 1];
pos = i - (1 << (j - 1));
if(pos >= 0)
segu[i][j] = max(segu[i][j], segu[pos][j - 1]);
}
}
for(int i = 0; i < w; i++)
segl[i][0] = segr[i][0] = b[i];
for(int j = 1; j < logn; j++){
for(int i = 0; i < w; i++){
segr[i][j] = segr[i][j - 1];
int pos = i + (1 << (j - 1));
if(pos < w)
segr[i][j] = max(segr[i][j], segr[pos][j - 1]);
segl[i][j] = segl[i][j - 1];
pos = i - (1 << (j - 1));
if(pos >= 0)
segl[i][j] = max(segl[i][j], segl[pos][j - 1]);
}
}
}
int main(){
scanf("%d%d%d", &h, &w, &q);
for(int i = 0; i < h; i++)
scanf("%d", a + i);
for(int i = 0; i < w; i++)
scanf("%d", b + i);
precalc();
while(q--){
int x, y, ans = 0;
scanf("%d%d", &x, &y);
x--; y--;
for(int i = 0; i < 4; i++)
ans = max(ans, f(x, y, i));
printf("%d\n", ans);
}
return 0;
}
Compilation message
abduction2.cpp: In function 'int main()':
abduction2.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &h, &w, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:143:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", a + i);
~~~~~^~~~~~~~~~~~~
abduction2.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", b + i);
~~~~~^~~~~~~~~~~~~
abduction2.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2312 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2312 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2312 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1954 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2312 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
