162892025-04-20 17:39:58horkaMágikus táblázatcpp17Accepted 100/100305ms13452 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m; cin>>n>>m;
    vector<int> a(n+1),b(m+1),pontok{(int)-1e9-10};
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        pontok.pb(a[i]);
    }
    for(int i=1; i<=m; i++)
    {
        cin>>b[i];
        pontok.pb(b[i]);
    }
    sort(all(pontok));
    pontok.erase(unique(all(pontok)),pontok.end());
    for(int i=1; i<=n; i++)
    {
        a[i]=lower_bound(all(pontok),a[i])-pontok.begin();
    }
    for(int i=1; i<=m; i++)
        b[i]=lower_bound(all(pontok),b[i])-pontok.begin();
    vector<array<int, 2>> op;
    for(int i=1; i<=m; i++)
        op.pb({b[i],i});
    sort(all(op));
    int mer=sz(pontok);
    vector<int> maxi(mer);
    set<int> s;
    for(int i=0; i<=m+1; i++)
        s.insert(i);
    for(auto &[ert,ind]:op)
    {
        s.erase(ind);
        auto l=s.lower_bound(ind),r=s.upper_bound(ind);
        l=prev(l);
        maxi[ert]=max(maxi[ert],*r-*l-1);
        //cout<<"itt: "<<ert<<" "<<ind<<" "<<*l<<" "<<*r<<endl;
    }
    for(int i=1; i<mer; i++)
        maxi[i]=max(maxi[i],maxi[i-1]);
    int ans=0;
    op.clear();
    for(int i=1; i<=n; i++)
        op.pb({a[i],i});
    sort(rall(op));
    s.clear();
    for(int i=0; i<=n+1; i++)
        s.insert(i);
    for(auto &[ert,ind]:op)
    {
        s.erase(ind);
        auto l=s.lower_bound(ind),r=s.upper_bound(ind);
        l=prev(l);
        ans=max(ans,(*r-*l-1)*maxi[ert]);
    }
    cout<<ans<<"\n";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted23ms1588 KiB
subtask214/14
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms500 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
8Accepted1ms316 KiB
subtask327/27
9Accepted4ms520 KiB
10Accepted4ms544 KiB
11Accepted4ms552 KiB
12Accepted4ms856 KiB
13Accepted3ms424 KiB
14Accepted2ms500 KiB
15Accepted3ms564 KiB
16Accepted4ms564 KiB
17Accepted4ms676 KiB
subtask421/21
18Accepted245ms10532 KiB
19Accepted240ms10660 KiB
20Accepted165ms10528 KiB
21Accepted159ms10660 KiB
22Accepted143ms9252 KiB
23Accepted143ms9252 KiB
24Accepted3ms564 KiB
subtask538/38
25Accepted305ms13348 KiB
26Accepted296ms13452 KiB
27Accepted301ms13348 KiB
28Accepted294ms13348 KiB
29Accepted212ms12676 KiB
30Accepted226ms12436 KiB
31Accepted172ms12332 KiB
32Accepted180ms8740 KiB
33Accepted175ms8740 KiB
34Accepted97ms7716 KiB
35Accepted148ms7972 KiB
36Accepted232ms12840 KiB
37Accepted233ms12580 KiB
38Accepted219ms12580 KiB
39Accepted296ms13348 KiB
40Accepted279ms13092 KiB
41Accepted231ms11300 KiB
42Accepted212ms12068 KiB
43Accepted177ms12324 KiB
44Accepted196ms12584 KiB