55732023-08-01 14:09:00111Mágikus táblázatcpp14Time limit exceeded 41/100600ms9192 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);
	int ans = 0;
	for (int i = 0; i < A; i++) {
		for (int j = 0; j < B; j++) {
			if (b[j] > a[i]) {
				continue;
			}
			ans = max(ans, (na[i] - pa[i] - 1) * (nb[j] - pb[j] - 1));
		}
	}
	cout << ans << endl;
	return 0;
}























SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1812 KiB
2Accepted453ms3040 KiB
subtask214/14
3Accepted3ms2136 KiB
4Accepted3ms2348 KiB
5Accepted3ms2572 KiB
6Accepted3ms2820 KiB
7Accepted3ms2972 KiB
8Accepted3ms3204 KiB
subtask327/27
9Accepted9ms3628 KiB
10Accepted9ms3840 KiB
11Accepted9ms3880 KiB
12Accepted8ms3796 KiB
13Accepted4ms3764 KiB
14Accepted4ms3764 KiB
15Accepted8ms3908 KiB
16Accepted10ms3776 KiB
17Accepted8ms4036 KiB
subtask40/21
18Time limit exceeded600ms7776 KiB
19Time limit exceeded574ms7788 KiB
20Time limit exceeded552ms8180 KiB
21Time limit exceeded573ms8208 KiB
22Time limit exceeded561ms7844 KiB
23Time limit exceeded550ms7860 KiB
24Accepted7ms4900 KiB
subtask50/38
25Time limit exceeded600ms8576 KiB
26Time limit exceeded561ms8728 KiB
27Time limit exceeded546ms8628 KiB
28Time limit exceeded565ms8720 KiB
29Time limit exceeded561ms8544 KiB
30Time limit exceeded561ms8464 KiB
31Time limit exceeded561ms8828 KiB
32Time limit exceeded577ms7176 KiB
33Time limit exceeded504ms7312 KiB
34Time limit exceeded541ms7392 KiB
35Time limit exceeded565ms7372 KiB
36Time limit exceeded564ms9012 KiB
37Time limit exceeded554ms8860 KiB
38Time limit exceeded533ms8952 KiB
39Time limit exceeded580ms8960 KiB
40Time limit exceeded578ms8804 KiB
41Time limit exceeded541ms8044 KiB
42Time limit exceeded560ms8732 KiB
43Time limit exceeded533ms8936 KiB
44Time limit exceeded565ms9192 KiB