55742023-08-01 14:28:15111Mágikus táblázatcpp14Time limit exceeded 41/100600ms7612 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;
	}
	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, da[i] * db[j]);
		}
	}
	cout << ans << endl;
	return 0;
}























SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1684 KiB
2Accepted428ms2544 KiB
subtask214/14
3Accepted3ms2064 KiB
4Accepted3ms2300 KiB
5Accepted3ms2552 KiB
6Accepted3ms2728 KiB
7Accepted3ms2912 KiB
8Accepted3ms2992 KiB
subtask327/27
9Accepted8ms3304 KiB
10Accepted8ms3260 KiB
11Accepted8ms3444 KiB
12Accepted8ms3764 KiB
13Accepted4ms3824 KiB
14Accepted4ms3852 KiB
15Accepted6ms4120 KiB
16Accepted8ms4352 KiB
17Accepted8ms4656 KiB
subtask40/21
18Time limit exceeded600ms6900 KiB
19Time limit exceeded558ms6840 KiB
20Time limit exceeded552ms6992 KiB
21Time limit exceeded556ms7152 KiB
22Time limit exceeded561ms6740 KiB
23Time limit exceeded565ms6920 KiB
24Accepted7ms4972 KiB
subtask50/38
25Time limit exceeded600ms7188 KiB
26Time limit exceeded565ms7116 KiB
27Time limit exceeded561ms7028 KiB
28Time limit exceeded565ms6952 KiB
29Time limit exceeded582ms7000 KiB
30Time limit exceeded564ms7308 KiB
31Time limit exceeded582ms7296 KiB
32Time limit exceeded573ms6380 KiB
33Time limit exceeded565ms6208 KiB
34Time limit exceeded549ms6528 KiB
35Time limit exceeded518ms6472 KiB
36Time limit exceeded554ms7580 KiB
37Time limit exceeded556ms7548 KiB
38Time limit exceeded569ms7552 KiB
39Time limit exceeded550ms7536 KiB
40Time limit exceeded558ms7356 KiB
41Time limit exceeded582ms6808 KiB
42Time limit exceeded574ms7416 KiB
43Time limit exceeded558ms7528 KiB
44Time limit exceeded550ms7612 KiB