#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;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Runtime error | 3ms | 1924 KiB | ||||
2 | Runtime error | 3ms | 2116 KiB | ||||
subtask2 | 0/9 | ||||||
3 | Runtime error | 3ms | 2340 KiB | ||||
4 | Runtime error | 3ms | 2592 KiB | ||||
5 | Runtime error | 3ms | 2736 KiB | ||||
6 | Runtime error | 3ms | 2852 KiB | ||||
7 | Runtime error | 3ms | 2948 KiB | ||||
8 | Runtime error | 3ms | 3316 KiB | ||||
subtask3 | 0/11 | ||||||
9 | Runtime error | 3ms | 3588 KiB | ||||
10 | Runtime error | 3ms | 3664 KiB | ||||
11 | Runtime error | 3ms | 3796 KiB | ||||
12 | Runtime error | 3ms | 4016 KiB | ||||
13 | Runtime error | 3ms | 4228 KiB | ||||
14 | Runtime error | 3ms | 4224 KiB | ||||
subtask4 | 0/13 | ||||||
15 | Runtime error | 3ms | 4096 KiB | ||||
16 | Runtime error | 3ms | 4252 KiB | ||||
17 | Runtime error | 3ms | 4488 KiB | ||||
18 | Runtime error | 3ms | 4424 KiB | ||||
19 | Runtime error | 3ms | 4548 KiB | ||||
20 | Runtime error | 3ms | 4608 KiB | ||||
subtask5 | 0/24 | ||||||
21 | Runtime error | 3ms | 4596 KiB | ||||
22 | Runtime error | 3ms | 4740 KiB | ||||
23 | Runtime error | 3ms | 4976 KiB | ||||
24 | Runtime error | 3ms | 4868 KiB | ||||
25 | Runtime error | 3ms | 5008 KiB | ||||
26 | Runtime error | 3ms | 4876 KiB | ||||
subtask6 | 0/43 | ||||||
27 | Runtime error | 3ms | 4892 KiB | ||||
28 | Runtime error | 3ms | 4896 KiB | ||||
29 | Runtime error | 3ms | 5024 KiB | ||||
30 | Runtime error | 3ms | 5064 KiB | ||||
31 | Runtime error | 3ms | 5176 KiB | ||||
32 | Runtime error | 3ms | 5112 KiB | ||||
33 | Runtime error | 3ms | 5040 KiB | ||||
34 | Runtime error | 3ms | 5056 KiB |