记录编号	577290	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2022S]策略游戏	最终得分	100
用户昵称	nick	是否通过	通过
代码语言	C++	运行时间	2.483 s
提交时间	2022-10-30 13:18:43	内存使用	54.86 MiB

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200051;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, q;
ll a[MAXN], b[MAXN];
ll mx[21][MAXN], mi[21][MAXN], mip[21][MAXN], mxn[21][MAXN];
ll getmax(ll st[21][MAXN], int l, int r){
    int lg = 31 - __builtin_clz(r - l + 1);
    return max(st[lg][l], st[lg][r - (1 << lg) + 1]);
}
ll getmin(ll st[21][MAXN], int l, int r){
    int lg = 31 - __builtin_clz(r - l + 1);
    return min(st[lg][l], st[lg][r - (1 << lg) + 1]);
}
ll wrk(ll s1, int l, int r){
    return (s1 < 0) ? s1 * getmax(mx, l + n, r + n) : s1 * getmin(mi, l + n, r + n);
}
int main(){
    ios::sync_with_stdio(false);
    freopen("csp2022_game.in", "r", stdin);
    freopen("csp2022_game.out", "w", stdout);
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> a[n + i];
    for (int i = 1; i <= n + m; i++){
        mx[0][i] = mi[0][i] = a[i];
        mip[0][i] = (a[i] >= 0) ? a[i] : INF;
        mxn[0][i] = (a[i] < 0) ? a[i] : -INF;
    }
    for (int j = 1; j <= 20; j++){
        for (int i = 1; i + (1 << j) - 1 <= n + m; i++){
            mx[j][i]=max(mx[j-1][i],mx[j-1][i+(1<<(j-1))]);
            mi[j][i]=min(mi[j-1][i],mi[j-1][i+(1<<(j-1))]);
            mip[j][i]=min(mip[j-1][i],mip[j-1][i+(1<<(j-1))]);
            mxn[j][i]=max(mxn[j-1][i],mxn[j-1][i+(1<<(j-1))]);
        }
    }
    while (q--){
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        ll ans = -INF;
        ans = max(ans, wrk(getmax(mx, l1, r1), l2, r2));
        ans = max(ans, wrk(getmin(mi, l1, r1), l2, r2));
        if (getmin(mip, l1, r1) != INF) ans = max(ans, wrk(getmin(mip, l1, r1), l2, r2));
        if (getmax(mxn, l1, r1) != -INF) ans = max(ans, wrk(getmax(mxn, l1, r1), l2, r2));
        cout << ans << '\n';
    }
    return 0;
}