55752023-08-01 14:35:00111Mágikus táblázatcpp14Hibás válasz 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;
}























RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1812 KiB
2Elfogadva14ms2784 KiB
subtask214/14
3Elfogadva3ms2120 KiB
4Elfogadva2ms2192 KiB
5Elfogadva3ms2428 KiB
6Elfogadva3ms2512 KiB
7Elfogadva2ms2528 KiB
8Elfogadva3ms2648 KiB
subtask327/27
9Elfogadva4ms3196 KiB
10Elfogadva4ms3088 KiB
11Elfogadva4ms3024 KiB
12Elfogadva4ms3028 KiB
13Elfogadva4ms3256 KiB
14Elfogadva4ms3464 KiB
15Elfogadva4ms3700 KiB
16Elfogadva4ms3916 KiB
17Elfogadva4ms3996 KiB
subtask421/21
18Elfogadva79ms11540 KiB
19Elfogadva79ms11368 KiB
20Elfogadva70ms11544 KiB
21Elfogadva68ms11368 KiB
22Elfogadva61ms10588 KiB
23Elfogadva59ms10540 KiB
24Elfogadva4ms4328 KiB
subtask50/38
25Elfogadva130ms12068 KiB
26Elfogadva136ms11992 KiB
27Elfogadva130ms11880 KiB
28Elfogadva128ms11904 KiB
29Elfogadva104ms11900 KiB
30Elfogadva122ms11904 KiB
31Elfogadva104ms11900 KiB
32Elfogadva81ms9416 KiB
33Elfogadva82ms9464 KiB
34Elfogadva67ms9388 KiB
35Elfogadva71ms9328 KiB
36Elfogadva118ms11928 KiB
37Elfogadva115ms12208 KiB
38Hibás válasz111ms12216 KiB
39Elfogadva127ms12220 KiB
40Elfogadva122ms11840 KiB
41Elfogadva100ms10716 KiB
42Elfogadva119ms11624 KiB
43Elfogadva105ms12160 KiB
44Elfogadva112ms12272 KiB