55762023-08-01 14:41:47111Mágikus táblázatcpp14Accepted 100/100141ms20668 KiB
#include <bits/extc++.h>
using namespace std;

#define int long long

#define pii pair<int, int>

void prev_greater(vector<int>& r, const vector<int>& a) {
	stack<int> s;
	for (int i = 0; i < a.size(); i++) {
		while (!s.empty() && a[s.top()] <= a[i]) {
			s.pop();
		}
		r[i] = s.empty() ? -1 : s.top();
		s.push(i);
	}
}

void prev_less(vector<int>& r, const vector<int>& a) {
	stack<int> s;
	for (int i = 0; i < a.size(); i++) {
		while (!s.empty() && a[s.top()] >= a[i]) {
			s.pop();
		}
		r[i] = s.empty() ? -1 : s.top();
		s.push(i);
	}
}

void next_greater(vector<int>& r, const vector<int>& a) {
	stack<int> s;
	for (int i = a.size() - 1; i >= 0; i--) {
		while (!s.empty() && a[s.top()] <= a[i]) {
			s.pop();
		}
		r[i] = s.empty() ? a.size() : s.top();
		s.push(i);
	}
}

void next_less(vector<int>& r, const vector<int>& a) {
	stack<int> s;
	for (int i = a.size() - 1; i >= 0; i--) {
		while (!s.empty() && a[s.top()] >= a[i]) {
			s.pop();
		}
		r[i] = s.empty() ? a.size() : s.top();
		s.push(i);
	}
}

signed main() {
#ifdef CB
	ifstream fin("be1.txt");
	cin.rdbuf(fin.rdbuf());
	ofstream fout("ki.txt");
#endif
	int A, B;
	cin >> A >> B;
	vector<int> a(A), b(B);
	for (int i = 0; i < A; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < B; i++) {
		cin >> b[i];
	}
	vector<int> pa(A), na(A);
	vector<int> pb(B), nb(B);
	prev_less(pa, a);
	next_less(na, a);
	prev_greater(pb, b);
	next_greater(nb, b);
	vector<int> da(A), db(B);
	for (int i = 0; i < A; i++) {
		da[i] = na[i] - pa[i] - 1;
	}
	for (int i = 0; i < B; i++) {
		db[i] = nb[i] - pb[i] - 1;
	}
	vector<int> ib(B);
	iota(ib.begin(), ib.end(), 0);
	sort(ib.begin(), ib.end(), [&](int i, int j) { return b[i] < b[j]; });
	vector<int> mb(B + 1);
	for (int i = 0; i < B; i++) {
		mb[i + 1] = max(mb[i], db[ib[i]]);
	}
	sort(b.begin(), b.end());
	int ans = 0;
	for (int i = 0; i < A; i++) {
		int j = upper_bound(b.begin(), b.end(), a[i]) - b.begin();
		ans = max(ans, da[i] * mb[j]);
	}
	cout << ans << endl;
	return 0;
}























SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1808 KiB
2Accepted14ms3608 KiB
subtask214/14
3Accepted3ms2152 KiB
4Accepted3ms2280 KiB
5Accepted3ms2492 KiB
6Accepted3ms2696 KiB
7Accepted3ms2908 KiB
8Accepted2ms2988 KiB
subtask327/27
9Accepted4ms3240 KiB
10Accepted4ms3368 KiB
11Accepted4ms3360 KiB
12Accepted4ms3512 KiB
13Accepted4ms3408 KiB
14Accepted4ms3628 KiB
15Accepted4ms3824 KiB
16Accepted4ms3872 KiB
17Accepted4ms3880 KiB
subtask421/21
18Accepted83ms19112 KiB
19Accepted82ms19368 KiB
20Accepted75ms19472 KiB
21Accepted72ms19532 KiB
22Accepted64ms17272 KiB
23Accepted64ms16836 KiB
24Accepted4ms4088 KiB
subtask538/38
25Accepted136ms19604 KiB
26Accepted141ms19808 KiB
27Accepted136ms19768 KiB
28Accepted135ms19772 KiB
29Accepted112ms19820 KiB
30Accepted127ms19884 KiB
31Accepted108ms19776 KiB
32Accepted83ms14728 KiB
33Accepted85ms14672 KiB
34Accepted71ms14620 KiB
35Accepted75ms14620 KiB
36Accepted123ms19944 KiB
37Accepted120ms19944 KiB
38Accepted118ms19944 KiB
39Accepted133ms19892 KiB
40Accepted128ms19296 KiB
41Accepted104ms16252 KiB
42Accepted125ms18984 KiB
43Accepted109ms19688 KiB
44Accepted116ms20668 KiB