52652023-04-24 20:08:42gortomiRegexcpp17Runtime error 0/1003ms5176 KiB
#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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Runtime error3ms1924 KiB
2Runtime error3ms2116 KiB
subtask20/9
3Runtime error3ms2340 KiB
4Runtime error3ms2592 KiB
5Runtime error3ms2736 KiB
6Runtime error3ms2852 KiB
7Runtime error3ms2948 KiB
8Runtime error3ms3316 KiB
subtask30/11
9Runtime error3ms3588 KiB
10Runtime error3ms3664 KiB
11Runtime error3ms3796 KiB
12Runtime error3ms4016 KiB
13Runtime error3ms4228 KiB
14Runtime error3ms4224 KiB
subtask40/13
15Runtime error3ms4096 KiB
16Runtime error3ms4252 KiB
17Runtime error3ms4488 KiB
18Runtime error3ms4424 KiB
19Runtime error3ms4548 KiB
20Runtime error3ms4608 KiB
subtask50/24
21Runtime error3ms4596 KiB
22Runtime error3ms4740 KiB
23Runtime error3ms4976 KiB
24Runtime error3ms4868 KiB
25Runtime error3ms5008 KiB
26Runtime error3ms4876 KiB
subtask60/43
27Runtime error3ms4892 KiB
28Runtime error3ms4896 KiB
29Runtime error3ms5024 KiB
30Runtime error3ms5064 KiB
31Runtime error3ms5176 KiB
32Runtime error3ms5112 KiB
33Runtime error3ms5040 KiB
34Runtime error3ms5056 KiB