#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 17
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
ll segd[maxn][logn], segu[maxn][logn], segl[maxn][logn], segr[maxn][logn];
ll a[maxn], b[maxn];
int h, w, q;
map<ll, ll> dp;
int findPos(int x, ll val, int n, int sign, ll 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;
}
ll f(int x, int y, int dir){
ll id = x * 2 * maxn + 2 * y + dir;
if(dp[id])
return dp[id];
// cout << x << " " << y << " " << dir << endl;
ll cur = 0;
if(dir == 0){ // left
int pos = findPos(y - 1, a[x], w, -1, segl);
ll dist = abs(pos - y);
if(pos < 0){
cur = max(cur, dist - 1);
}
else{
cur = max(cur, f(x, pos, 1) + dist);
cur = max(cur, f(x, pos, 1) + dist);
}
}
if(dir == 0){ // right
int pos = findPos(y + 1, a[x], w, 1, segr);
ll dist = abs(pos - y);
if(pos == w){
cur = max(cur, dist - 1);
}
else{
cur = max(cur, f(x, pos, 1) + dist);
cur = max(cur, f(x, pos, 1) + dist);
}
}
if(dir == 1){ // down
int pos = findPos(x + 1, b[y], h, 1, segd);
ll dist = abs(pos - x);
if(pos == h){
cur = max(cur, dist - 1);
}
else{
cur = max(cur, f(pos, y, 0) + dist);
cur = max(cur, f(pos, y, 0) + dist);
}
}
if(dir == 1){ // up
int pos = findPos(x - 1, b[y], h, -1, segu);
ll dist = abs(pos - x);
if(pos < 0){
cur = max(cur, dist - 1);
}
else{
cur = max(cur, f(pos, y, 0) + dist);
cur = max(cur, f(pos, y, 0) + dist);
}
}
return dp[id] = 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 - 1], 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("%lld", a + i);
for(int i = 0; i < w; i++)
scanf("%lld", b + i);
precalc();
while(q--){
int x, y;
ll ans = 0;
scanf("%d%d", &x, &y);
x--; y--;
for(int i = 0; i < 2; i++)
ans = max(ans, f(x, y, i));
printf("%lld\n", ans);
}
return 0;
}
Compilation message
abduction2.cpp: In function 'int main()':
abduction2.cpp:147: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:149:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", a + i);
~~~~~^~~~~~~~~~~~~~~
abduction2.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", b + i);
~~~~~^~~~~~~~~~~~~~~
abduction2.cpp:159: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 |
1785 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 |
1785 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 |
1785 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 |
1593 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 |
1785 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
