5576 2023. 08. 01 14:41:47 111 Mágikus táblázat cpp14 Elfogadva 100/100 141ms 20668 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;
}























Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1808 KiB
2 Elfogadva 14ms 3608 KiB
subtask2 14/14
3 Elfogadva 3ms 2152 KiB
4 Elfogadva 3ms 2280 KiB
5 Elfogadva 3ms 2492 KiB
6 Elfogadva 3ms 2696 KiB
7 Elfogadva 3ms 2908 KiB
8 Elfogadva 2ms 2988 KiB
subtask3 27/27
9 Elfogadva 4ms 3240 KiB
10 Elfogadva 4ms 3368 KiB
11 Elfogadva 4ms 3360 KiB
12 Elfogadva 4ms 3512 KiB
13 Elfogadva 4ms 3408 KiB
14 Elfogadva 4ms 3628 KiB
15 Elfogadva 4ms 3824 KiB
16 Elfogadva 4ms 3872 KiB
17 Elfogadva 4ms 3880 KiB
subtask4 21/21
18 Elfogadva 83ms 19112 KiB
19 Elfogadva 82ms 19368 KiB
20 Elfogadva 75ms 19472 KiB
21 Elfogadva 72ms 19532 KiB
22 Elfogadva 64ms 17272 KiB
23 Elfogadva 64ms 16836 KiB
24 Elfogadva 4ms 4088 KiB
subtask5 38/38
25 Elfogadva 136ms 19604 KiB
26 Elfogadva 141ms 19808 KiB
27 Elfogadva 136ms 19768 KiB
28 Elfogadva 135ms 19772 KiB
29 Elfogadva 112ms 19820 KiB
30 Elfogadva 127ms 19884 KiB
31 Elfogadva 108ms 19776 KiB
32 Elfogadva 83ms 14728 KiB
33 Elfogadva 85ms 14672 KiB
34 Elfogadva 71ms 14620 KiB
35 Elfogadva 75ms 14620 KiB
36 Elfogadva 123ms 19944 KiB
37 Elfogadva 120ms 19944 KiB
38 Elfogadva 118ms 19944 KiB
39 Elfogadva 133ms 19892 KiB
40 Elfogadva 128ms 19296 KiB
41 Elfogadva 104ms 16252 KiB
42 Elfogadva 125ms 18984 KiB
43 Elfogadva 109ms 19688 KiB
44 Elfogadva 116ms 20668 KiB