55762023-08-01 14:41:47111Mágikus táblázatcpp14Elfogadva 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;
}























RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1808 KiB
2Elfogadva14ms3608 KiB
subtask214/14
3Elfogadva3ms2152 KiB
4Elfogadva3ms2280 KiB
5Elfogadva3ms2492 KiB
6Elfogadva3ms2696 KiB
7Elfogadva3ms2908 KiB
8Elfogadva2ms2988 KiB
subtask327/27
9Elfogadva4ms3240 KiB
10Elfogadva4ms3368 KiB
11Elfogadva4ms3360 KiB
12Elfogadva4ms3512 KiB
13Elfogadva4ms3408 KiB
14Elfogadva4ms3628 KiB
15Elfogadva4ms3824 KiB
16Elfogadva4ms3872 KiB
17Elfogadva4ms3880 KiB
subtask421/21
18Elfogadva83ms19112 KiB
19Elfogadva82ms19368 KiB
20Elfogadva75ms19472 KiB
21Elfogadva72ms19532 KiB
22Elfogadva64ms17272 KiB
23Elfogadva64ms16836 KiB
24Elfogadva4ms4088 KiB
subtask538/38
25Elfogadva136ms19604 KiB
26Elfogadva141ms19808 KiB
27Elfogadva136ms19768 KiB
28Elfogadva135ms19772 KiB
29Elfogadva112ms19820 KiB
30Elfogadva127ms19884 KiB
31Elfogadva108ms19776 KiB
32Elfogadva83ms14728 KiB
33Elfogadva85ms14672 KiB
34Elfogadva71ms14620 KiB
35Elfogadva75ms14620 KiB
36Elfogadva123ms19944 KiB
37Elfogadva120ms19944 KiB
38Elfogadva118ms19944 KiB
39Elfogadva133ms19892 KiB
40Elfogadva128ms19296 KiB
41Elfogadva104ms16252 KiB
42Elfogadva125ms18984 KiB
43Elfogadva109ms19688 KiB
44Elfogadva116ms20668 KiB