103252024-03-30 21:23:05szilMágikus táblázatcpp17Accepted 100/10071ms54780 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 100'001;

int a[MAXN], b[MAXN], bef[MAXN], aft[MAXN], par[MAXN], siz[MAXN], biggest = 1;

int holvan(int u) {
	return par[u] == u ? u : par[u] = holvan(par[u]);
}

void unio(int u, int v) {
	u = holvan(u); v = holvan(v);
	if (u == v) return;
	siz[u] += siz[v];
	biggest = max(biggest, siz[u]);
	par[v] = u;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;

	iota(par, par+MAXN, 0);
	fill(siz, siz+MAXN, 1);

	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++) cin >> b[i];

	vector<int> indices(n);
	iota(indices.begin(), indices.end(), 1);
	sort(indices.begin(), indices.end(), [&](int i, int j){
		return a[i] < a[j];
	});

	stack<int> st;
	for (int i = 1; i <= n; i++) {
		while (!st.empty() && a[st.top()] >= a[i]) st.pop();
		bef[i] = st.empty() ? 0 : st.top();
		st.push(i);
	}
	st = stack<int>();
	for (int i = n; i >= 1; i--) {
		while (!st.empty() && a[st.top()] >= a[i]) st.pop();
		aft[i] = st.empty() ? n+1 : st.top();
		st.push(i);
	}

	int mine = *min_element(b+1, b+m+1);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

	for (int i = 1; i < m; i++) {
		int w = max(b[i], b[i+1]);
		pq.push({w, i});
	}

	ll ans = 0;
	for (int i : indices) {
		if (a[i] < mine) continue;
		while (!pq.empty() && pq.top().first <= a[i]) {
			unio(pq.top().second, pq.top().second+1);
			pq.pop();
		}
		ll len = (aft[i] - bef[i] - 1);
		ans = max(ans, len * biggest);
	}

	cout << ans << "\n";

	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms3520 KiB
2Accepted9ms4668 KiB
subtask214/14
3Accepted3ms4340 KiB
4Accepted3ms4404 KiB
5Accepted3ms4680 KiB
6Accepted3ms4800 KiB
7Accepted3ms4664 KiB
8Accepted3ms4976 KiB
subtask327/27
9Accepted4ms5392 KiB
10Accepted4ms5520 KiB
11Accepted4ms5536 KiB
12Accepted4ms5884 KiB
13Accepted4ms5876 KiB
14Accepted4ms6304 KiB
15Accepted4ms6200 KiB
16Accepted4ms6252 KiB
17Accepted4ms6296 KiB
subtask421/21
18Accepted59ms12924 KiB
19Accepted45ms13816 KiB
20Accepted48ms14704 KiB
21Accepted45ms15652 KiB
22Accepted41ms15928 KiB
23Accepted41ms17236 KiB
24Accepted4ms11956 KiB
subtask538/38
25Accepted71ms19724 KiB
26Accepted71ms21760 KiB
27Accepted71ms23816 KiB
28Accepted71ms26016 KiB
29Accepted65ms28040 KiB
30Accepted41ms29960 KiB
31Accepted61ms31792 KiB
32Accepted46ms31700 KiB
33Accepted35ms32968 KiB
34Accepted34ms34260 KiB
35Accepted41ms35292 KiB
36Accepted68ms38792 KiB
37Accepted67ms40864 KiB
38Accepted64ms43152 KiB
39Accepted54ms45344 KiB
40Accepted50ms46780 KiB
41Accepted45ms48180 KiB
42Accepted39ms50720 KiB
43Accepted50ms52548 KiB
44Accepted52ms54780 KiB