52662023-04-24 20:09:14gortomiMágikus táblázatcpp17Accepted 100/10059ms10356 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
1Accepted3ms1832 KiB
2Accepted8ms2488 KiB
subtask214/14
3Accepted3ms2380 KiB
4Accepted3ms2592 KiB
5Accepted3ms2804 KiB
6Accepted3ms2752 KiB
7Accepted2ms2836 KiB
8Accepted3ms3064 KiB
subtask327/27
9Accepted3ms3456 KiB
10Accepted3ms3668 KiB
11Accepted3ms3620 KiB
12Accepted3ms3780 KiB
13Accepted3ms3988 KiB
14Accepted3ms4192 KiB
15Accepted3ms4168 KiB
16Accepted3ms4172 KiB
17Accepted3ms4444 KiB
subtask421/21
18Accepted45ms8644 KiB
19Accepted45ms8644 KiB
20Accepted37ms8640 KiB
21Accepted35ms8640 KiB
22Accepted32ms8888 KiB
23Accepted35ms8336 KiB
24Accepted3ms4520 KiB
subtask538/38
25Accepted54ms8900 KiB
26Accepted59ms9160 KiB
27Accepted54ms9264 KiB
28Accepted54ms9276 KiB
29Accepted48ms9208 KiB
30Accepted41ms9500 KiB
31Accepted45ms9500 KiB
32Accepted35ms7972 KiB
33Accepted34ms7900 KiB
34Accepted26ms7900 KiB
35Accepted37ms7856 KiB
36Accepted52ms9420 KiB
37Accepted50ms10332 KiB
38Accepted50ms10356 KiB
39Accepted50ms9592 KiB
40Accepted48ms10060 KiB
41Accepted43ms8988 KiB
42Accepted39ms9420 KiB
43Accepted41ms10060 KiB
44Accepted43ms9564 KiB