55732023-08-01 14:09:00111Mágikus táblázatcpp14Időlimit túllépés 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;
}























RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1812 KiB
2Elfogadva453ms3040 KiB
subtask214/14
3Elfogadva3ms2136 KiB
4Elfogadva3ms2348 KiB
5Elfogadva3ms2572 KiB
6Elfogadva3ms2820 KiB
7Elfogadva3ms2972 KiB
8Elfogadva3ms3204 KiB
subtask327/27
9Elfogadva9ms3628 KiB
10Elfogadva9ms3840 KiB
11Elfogadva9ms3880 KiB
12Elfogadva8ms3796 KiB
13Elfogadva4ms3764 KiB
14Elfogadva4ms3764 KiB
15Elfogadva8ms3908 KiB
16Elfogadva10ms3776 KiB
17Elfogadva8ms4036 KiB
subtask40/21
18Időlimit túllépés600ms7776 KiB
19Időlimit túllépés574ms7788 KiB
20Időlimit túllépés552ms8180 KiB
21Időlimit túllépés573ms8208 KiB
22Időlimit túllépés561ms7844 KiB
23Időlimit túllépés550ms7860 KiB
24Elfogadva7ms4900 KiB
subtask50/38
25Időlimit túllépés600ms8576 KiB
26Időlimit túllépés561ms8728 KiB
27Időlimit túllépés546ms8628 KiB
28Időlimit túllépés565ms8720 KiB
29Időlimit túllépés561ms8544 KiB
30Időlimit túllépés561ms8464 KiB
31Időlimit túllépés561ms8828 KiB
32Időlimit túllépés577ms7176 KiB
33Időlimit túllépés504ms7312 KiB
34Időlimit túllépés541ms7392 KiB
35Időlimit túllépés565ms7372 KiB
36Időlimit túllépés564ms9012 KiB
37Időlimit túllépés554ms8860 KiB
38Időlimit túllépés533ms8952 KiB
39Időlimit túllépés580ms8960 KiB
40Időlimit túllépés578ms8804 KiB
41Időlimit túllépés541ms8044 KiB
42Időlimit túllépés560ms8732 KiB
43Időlimit túllépés533ms8936 KiB
44Időlimit túllépés565ms9192 KiB