#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#ifndef LOCAL
#define //cerr if(false) //cerr
#endif
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for(ll i = 0; i < n; i ++)
#define revn(i, n) for(ll i = n - 1; i >= 0; i --)
typedef long long ll;
template<class T, template<class T2, class A=allocator<T2> > class cont> inline ostream &operator <<(ostream &out, const cont<T> &x) { for(const auto &it : x) { out << it << " ";} return out;}
template<class T, template<class T2, class A=allocator<T2> > class cont> inline istream &operator >>(istream &in, cont<T> &x) { for(auto &it : x) { in >> it;} return in;}
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
const ll MAX_N = 1e5 + 10, MAX_LOG = 20;
ll a[MAX_N], b[MAX_N];
ll n, m, q;
map<pair<ll, ll>, ll> dp[4];
ll rmqa[MAX_N][MAX_LOG], rmqb[MAX_N][MAX_LOG];
void prec() {
forn(i, n) {
rmqa[i][0] = a[i];
}
for(ll l = 1; l < MAX_LOG; l ++) {
forn(i, n) {
rmqa[i][l] = rmqa[i][l - 1];
if(i + (1 << (l - 1)) < n) {
chkmax(rmqa[i][l], rmqa[i + (1 << (l - 1))][l - 1]);
}
}
}
forn(i, m) {
rmqb[i][0] = b[i];
}
for(ll l = 1; l < MAX_LOG; l ++) {
forn(i, n) {
rmqb[i][l] = rmqb[i][l - 1];
if(i + (1 << (l - 1)) < m) {
chkmax(rmqb[i][l], rmqb[i + (1 << (l - 1))][l - 1]);
}
}
}
}
ll solve(ll x, ll y, ll dir) {
//cerr << x << " " << y << " " << dir << endl;
if(x < 0 || y < 0 || x >= n || y >= m) {
while(true) {
}
}
if(dp[dir].find({x, y}) != dp[dir].end()) {
return dp[dir][{x, y}];
}
if(dir == 0) { // Right;
ll nowCost = a[x];
//cerr << nowCost << endl;
ll nxt = y;
revn(l, MAX_LOG) {
if(nowCost > rmqb[nxt][l]) {
nxt += (1 << l);
}
if(nxt >= m) {
return dp[dir][{x, y}] = m - 1 - y;
}
}
return dp[dir][{x, y}] = nxt - y + max(solve(x, nxt, 1), solve(x, nxt, 3));
} else
if(dir == 1) { // Down;
ll nowCost = b[y];
//cerr << nowCost << endl;
ll nxt = x;
revn(l, MAX_LOG) {
if(nowCost > rmqa[nxt][l]) {
nxt += (1 << l);
}
if(nxt >= n) {
return dp[dir][{x, y}] = n - 1 - x;
}
}
//cerr << "going to " << nxt << endl;
return dp[dir][{x, y}] = nxt - x + max(solve(nxt, y, 0), solve(nxt, y, 2));
} else
if(dir == 2) { // Left;
ll nowCost = a[x];
//cerr << nowCost << endl;
ll nxt = y;
revn(l, MAX_LOG) {
if(nxt - (1 << l) + 1 < 0) {continue;}
if(nowCost > rmqb[nxt - (1 << l) + 1][l]) {
nxt -= (1 << l);
}
if(nxt < 0) {
return dp[dir][{x, y}] = y;
}
}
return dp[dir][{x, y}] = y - nxt + max(solve(x, nxt, 1), solve(x, nxt, 3));
} else
if(dir == 3) { // Up;
ll nowCost = b[y];
//cerr << nowCost << endl;
ll nxt = x;
revn(l, MAX_LOG) {
if(nxt - (1 << l) + 1 < 0) {continue;}
if(nowCost > rmqa[nxt - (1 << l) + 1][l]) {
nxt -= (1 << l);
}
if(nxt < 0) {
return dp[dir][{x, y}] = x;
}
}
return dp[dir][{x, y}] = x - nxt + max(solve(nxt, y, 2), solve(nxt, y, 0));
}
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m >> q;
forn(i, n) {
cin >> a[i];
}
forn(i, m) {
cin >> b[i];
}
prec();
while(q --) {
ll x, y;
cin >> x >> y;
x --;
y --;
ll ret = 0;
if(x != n - 1) {
chkmax(ret, solve(x + 1, y, 1));
}
if(x != 0) {
chkmax(ret, solve(x - 1, y, 3));
}
if(y != m - 1) {
chkmax(ret, solve(x, y + 1, 0));
}
if(y != 0) {
chkmax(ret, solve(x, y - 1, 2));
}
cout << ret + 1 << endl;
}
return 0;
forn(dir, 4) {
cout << dir << endl;
for(auto it : dp[dir]) {
cout << "[" << it.first << "] " << it.second << endl;
}
}
return 0;
}
Compilation message
abduction2.cpp:6:32: error: no macro name given in #define directive
6 | #define //cerr if(false) //cerr
| ^
abduction2.cpp: In function 'll solve(ll, ll, ll)':
abduction2.cpp:125:1: warning: control reaches end of non-void function [-Wreturn-type]
125 | }
| ^
