#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> a(n + 2, -INT_MAX), b(m + 2, -INT_MAX);
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= m; i++)
{
cin >> b[i];
b[i] *= -1;
}
stack<int> s;
s.push(0);
vector<int> l(n + 1), r(n + 1);
for(int i = 1; i <= n; i++)
{
while(a[s.top()] >= a[i]) s.pop();
l[i] = s.top();
s.push(i);
}
while(!s.empty()) s.pop();
s.push(n + 1);
for(int i = n; i >= 1; i--)
{
while(a[s.top()] >= a[i]) s.pop();
r[i] = s.top();
s.push(i);
}
vector<pair<int, int> > v(n);
for(int i = 1; i <= n; i++)
{
v[i - 1] = {a[i], r[i] - l[i] - 1};
}
sort(v.begin(), v.end());
for(int i = n - 2; i >= 0; i--)
{
v[i].second = max(v[i + 1].second, v[i].second);
}
while(!s.empty()) s.pop();
l.assign(m + 1, 0);
r.assign(m + 1, 0);
s.push(0);
for(int i = 1; i <= m; i++)
{
while(b[s.top()] >= b[i]) s.pop();
l[i] = s.top();
s.push(i);
}
while(!s.empty()) s.pop();
s.push(m + 1);
for(int i = m; i >= 1; i--)
{
while(b[s.top()] >= b[i]) s.pop();
r[i] = s.top();
s.push(i);
}
long long ans = 0;
for(int i = 1; i <= m; i++)
{
auto x = lower_bound(v.begin(), v.end(), make_pair(-b[i], 0));
if(x == v.end()) continue;
long long z = x -> second;
z *= r[i] - l[i] - 1;
ans = max(ans, z);
}
cout << ans;
}
| Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Futási hiba | 3ms | 1924 KiB | ||||
| 2 | Futási hiba | 3ms | 2116 KiB | ||||
| subtask2 | 0/9 | ||||||
| 3 | Futási hiba | 3ms | 2340 KiB | ||||
| 4 | Futási hiba | 3ms | 2592 KiB | ||||
| 5 | Futási hiba | 3ms | 2736 KiB | ||||
| 6 | Futási hiba | 3ms | 2852 KiB | ||||
| 7 | Futási hiba | 3ms | 2948 KiB | ||||
| 8 | Futási hiba | 3ms | 3316 KiB | ||||
| subtask3 | 0/11 | ||||||
| 9 | Futási hiba | 3ms | 3588 KiB | ||||
| 10 | Futási hiba | 3ms | 3664 KiB | ||||
| 11 | Futási hiba | 3ms | 3796 KiB | ||||
| 12 | Futási hiba | 3ms | 4016 KiB | ||||
| 13 | Futási hiba | 3ms | 4228 KiB | ||||
| 14 | Futási hiba | 3ms | 4224 KiB | ||||
| subtask4 | 0/13 | ||||||
| 15 | Futási hiba | 3ms | 4096 KiB | ||||
| 16 | Futási hiba | 3ms | 4252 KiB | ||||
| 17 | Futási hiba | 3ms | 4488 KiB | ||||
| 18 | Futási hiba | 3ms | 4424 KiB | ||||
| 19 | Futási hiba | 3ms | 4548 KiB | ||||
| 20 | Futási hiba | 3ms | 4608 KiB | ||||
| subtask5 | 0/24 | ||||||
| 21 | Futási hiba | 3ms | 4596 KiB | ||||
| 22 | Futási hiba | 3ms | 4740 KiB | ||||
| 23 | Futási hiba | 3ms | 4976 KiB | ||||
| 24 | Futási hiba | 3ms | 4868 KiB | ||||
| 25 | Futási hiba | 3ms | 5008 KiB | ||||
| 26 | Futási hiba | 3ms | 4876 KiB | ||||
| subtask6 | 0/43 | ||||||
| 27 | Futási hiba | 3ms | 4892 KiB | ||||
| 28 | Futási hiba | 3ms | 4896 KiB | ||||
| 29 | Futási hiba | 3ms | 5024 KiB | ||||
| 30 | Futási hiba | 3ms | 5064 KiB | ||||
| 31 | Futási hiba | 3ms | 5176 KiB | ||||
| 32 | Futási hiba | 3ms | 5112 KiB | ||||
| 33 | Futási hiba | 3ms | 5040 KiB | ||||
| 34 | Futási hiba | 3ms | 5056 KiB | ||||