记录编号	577283	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2022S]策略游戏	最终得分	100
用户昵称	HeSn	是否通过	通过
代码语言	C++	运行时间	3.870 s
提交时间	2022-10-30 12:32:06	内存使用	3.53 MiB

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 100010;
int n, m, q, s, a[MAXN], b[MAXN];
int maxn1a[500], maxn2a[500], minn1a[500], minn2a[500], is0a[MAXN];
int maxn1b[500], maxn2b[500], minn1b[500], minn2b[500], is0b[MAXN];
struct node {
	int maxn1, maxn2, minn1, minn2, is0;
};
node query1(int x, int y) {
	int ka = x / s, kb = y / s;
//	cout << (ka + 1) * s << ' ' << kb * s << ' ';
	node ans;
	ans.maxn2 = -0x3f3f3f3f3f3f3f3f;
	ans.minn1 = 0x3f3f3f3f3f3f3f3f;
	ans.maxn1 = 0;
	ans.minn2 = 0;
	if(ka == kb) {
//		cout << 1111111 << ' ' ;
		for(int i = x; i <= y; i ++) {
			if(a[i] < 0) {
				ans.maxn2 = max(ans.maxn2, a[i]);
				ans.minn2 = min(ans.minn2, a[i]);
			}
			if(a[i] > 0) {
				ans.maxn1 = max(ans.maxn1, a[i]);
				ans.minn1 = min(ans.minn1, a[i]);
			}
		}
		return ans;
	}
	for(int i = x; i < (ka + 1) * s; i ++) {
		if(a[i] < 0) {
			ans.maxn2 = max(ans.maxn2, a[i]);
			ans.minn2 = min(ans.minn2, a[i]);
		}
		if(a[i] > 0) {
			ans.maxn1 = max(ans.maxn1, a[i]);
			ans.minn1 = min(ans.minn1, a[i]);
		}
	}
	for(int i = kb * s; i <= y; i ++) {
		if(a[i] < 0) {
			ans.maxn2 = max(ans.maxn2, a[i]);
			ans.minn2 = min(ans.minn2, a[i]);
		}
		if(a[i] > 0) {
			ans.maxn1 = max(ans.maxn1, a[i]);
			ans.minn1 = min(ans.minn1, a[i]);
		}
	}
	for(int i = ka + 1; i < kb; i ++) {
		ans.maxn2 = max(ans.maxn2, maxn2a[i]);
		ans.minn2 = min(ans.minn2, minn2a[i]);
		ans.maxn1 = max(ans.maxn1, maxn1a[i]);
		ans.minn1 = min(ans.minn1, minn1a[i]);
	}
	return ans;
}

node query2(int x, int y) {
	int ka = x / s, kb = y / s;
//	cout << (ka + 1) * s << ' ' << kb * s << ' ';
	node ans;
	ans.maxn2 = -0x3f3f3f3f3f3f3f3f;
	ans.minn1 = 0x3f3f3f3f3f3f3f3f;
	ans.maxn1 = 0;
	ans.minn2 = 0;
	if(ka == kb) {
//		cout << 1111111 << ' ' ;
		for(int i = x; i <= y; i ++) {
			if(b[i] < 0) {
				ans.maxn2 = max(ans.maxn2, b[i]);
				ans.minn2 = min(ans.minn2, b[i]);
			}
			if(b[i] > 0) {
				ans.maxn1 = max(ans.maxn1, b[i]);
				ans.minn1 = min(ans.minn1, b[i]);
			}
		}
		return ans;
	}
	for(int i = x; i < (ka + 1) * s; i ++) {
		if(b[i] < 0) {
			ans.maxn2 = max(ans.maxn2, b[i]);
			ans.minn2 = min(ans.minn2, b[i]);
		}
		if(b[i] > 0) {
			ans.maxn1 = max(ans.maxn1, b[i]);
			ans.minn1 = min(ans.minn1, b[i]);
		}
	}
	for(int i = kb * s; i <= y; i ++) {
		if(b[i] < 0) {
			ans.maxn2 = max(ans.maxn2, b[i]);
			ans.minn2 = min(ans.minn2, b[i]);
		}
		if(b[i] > 0) {
			ans.maxn1 = max(ans.maxn1, b[i]);
			ans.minn1 = min(ans.minn1, b[i]);
		}
	}
	for(int i = ka + 1; i < kb; i ++) {
		ans.maxn2 = max(ans.maxn2, maxn2b[i]);
		ans.minn2 = min(ans.minn2, minn2b[i]);
		ans.maxn1 = max(ans.maxn1, maxn1b[i]);
		ans.minn1 = min(ans.minn1, minn1b[i]);
	}
	return ans;
}
signed main() {
	freopen("csp2022_game.in", "r", stdin);
	freopen("csp2022_game.out", "w", stdout);
	cin >> n >> m >> q;
	s = sqrt(n);
	memset(maxn2a, -0x3f, sizeof(maxn2a));
	memset(minn1a, 0x3f, sizeof(minn1a));
	memset(maxn2b, -0x3f, sizeof(maxn2b));
	memset(minn1b, 0x3f, sizeof(minn1b));
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
		is0a[i] = is0a[i - 1];
		if(a[i] == 0) {
			is0a[i] ++;
		}
		if(a[i] < 0) {
			maxn2a[i / s] = max(maxn2a[i / s], a[i]);
			minn2a[i / s] = min(minn2a[i / s], a[i]);
		}
		if(a[i] > 0) {
			maxn1a[i / s] = max(maxn1a[i / s], a[i]);
			minn1a[i / s] = min(minn1a[i / s], a[i]);
		}
	}
	for(int i = 1; i <= m; i ++) {
		cin >> b[i];
		is0b[i] = is0b[i - 1];
		if(b[i] == 0) {
			is0b[i] ++;
		}
		if(b[i] < 0) {
			maxn2b[i / s] = max(maxn2b[i / s], b[i]);
			minn2b[i / s] = min(minn2b[i / s], b[i]);
		}
		if(b[i] > 0) {
			maxn1b[i / s] = max(maxn1b[i / s], b[i]);
			minn1b[i / s] = min(minn1b[i / s], b[i]);
		}
	}
	for(int i = 1; i <= q; i ++) {
		int l1, l2, r1, r2, ans = -0x3f3f3f3f3f3f3f3f;
		cin >> l1 >> r1 >> l2 >> r2;
		node ans1 = query1(l1, r1);
		ans1.is0 = is0a[r1] - is0a[l1 - 1];
		node ans2 = query2(l2, r2);
		ans2.is0 = is0b[r2] - is0b[l2 - 1];
		if(ans1.is0) {
			ans = 0;
		}
		if(ans1.maxn1) {
			if(ans2.minn2) {
				ans = max(ans, ans1.minn1 * ans2.minn2);
			}
			else if(ans2.is0) {
				ans = max(ans, (int)0);
			}
			else {
				ans = max(ans, ans1.maxn1 * ans2.minn1);
			}
		}
		if(ans1.minn2) {
			if(ans2.maxn1) {
				ans = max(ans, ans1.maxn2 * ans2.maxn1);
			}
			else if(ans2.is0) {
				ans = max(ans, (int)0);
			}
			else {
				ans = max(ans, ans1.minn2 * ans2.maxn2);
			}
		}
		cout << ans << endl;
//		cout << ans1.is0 << ' ' << ans1.maxn1 << ' ' << ans1.minn1 << ' ' << ans1.maxn2 << ' ' << ans1.minn2 << endl;
//		cout << ans2.is0 << ' ' << ans2.maxn1 << ' ' << ans2.minn1 << ' ' << ans2.maxn2 << ' ' << ans2.minn2 << endl;
	}
	return 0;
}