55752023-08-01 14:35:00111Mágikus táblázatcpp14Wrong answer 62/100136ms12272 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("be2.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++) {
		auto j = upper_bound(b.begin(), b.end(), a[i]);
		ans = max(ans, da[i] * mb[j - b.begin()]);
	}
	cout << ans << endl;
	return 0;
}























SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1812 KiB
2Accepted14ms2784 KiB
subtask214/14
3Accepted3ms2120 KiB
4Accepted2ms2192 KiB
5Accepted3ms2428 KiB
6Accepted3ms2512 KiB
7Accepted2ms2528 KiB
8Accepted3ms2648 KiB
subtask327/27
9Accepted4ms3196 KiB
10Accepted4ms3088 KiB
11Accepted4ms3024 KiB
12Accepted4ms3028 KiB
13Accepted4ms3256 KiB
14Accepted4ms3464 KiB
15Accepted4ms3700 KiB
16Accepted4ms3916 KiB
17Accepted4ms3996 KiB
subtask421/21
18Accepted79ms11540 KiB
19Accepted79ms11368 KiB
20Accepted70ms11544 KiB
21Accepted68ms11368 KiB
22Accepted61ms10588 KiB
23Accepted59ms10540 KiB
24Accepted4ms4328 KiB
subtask50/38
25Accepted130ms12068 KiB
26Accepted136ms11992 KiB
27Accepted130ms11880 KiB
28Accepted128ms11904 KiB
29Accepted104ms11900 KiB
30Accepted122ms11904 KiB
31Accepted104ms11900 KiB
32Accepted81ms9416 KiB
33Accepted82ms9464 KiB
34Accepted67ms9388 KiB
35Accepted71ms9328 KiB
36Accepted118ms11928 KiB
37Accepted115ms12208 KiB
38Wrong answer111ms12216 KiB
39Accepted127ms12220 KiB
40Accepted122ms11840 KiB
41Accepted100ms10716 KiB
42Accepted119ms11624 KiB
43Accepted105ms12160 KiB
44Accepted112ms12272 KiB