31542023-02-20 22:37:49zsomborMágikus táblázatcpp17Accepted 100/100268ms72360 KiB
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;

struct upd {
    int val, ab, ind;
};

struct node {
    int lft, mid, rgt;
    ll pref, lng, suff;
};

int n, m;
ll ans = 0;
vector <upd> U;
vector <node> sgt1(4e5);
vector <node> sgt2(4e5);

bool smaller(upd a, upd b) {
    if (a.val < b.val) return true;
    if (a.val > b.val) return false;
    return (a.ab > b.ab ? true : false);
}

void build1(int x, int l, int r) {
    node& N = sgt1[x];
    N.lft = l;
    N.mid = (l + r) / 2;
    N.rgt = r;
    N.pref = N.lng = N.suff = r - l;
    if (r - l == 1) return;
    build1(2 * x, l, N.mid);
    build1(2 * x + 1, N.mid, r);
}

void build2(int x, int l, int r) {
    node& N = sgt2[x];
    N.lft = l;
    N.rgt = r;
    N.mid = (l + r) / 2;
    N.pref = N.lng = N.suff = 0;
    if (r - l == 1) return;
    build2(2 * x, l, N.mid);
    build2(2 * x + 1, N.mid, r);
}

void update1(int x, int i) {
    node& N = sgt1[x];
    if (N.rgt - N.lft == 1) {
        N.pref = N.lng = N.suff = 0;
        return;
    }
    (i < N.mid ? update1(2 * x, i) : update1(2 * x + 1, i));
    node& N1 = sgt1[2 * x];
    node& N2 = sgt1[2 * x + 1];
    N.pref = (N1.pref < N1.rgt - N1.lft ? N1.pref : N1.pref + N2.pref);
    N.lng = max(N1.suff + N2.pref, max(N1.lng, N2.lng));
    N.suff = (N2.suff < N2.rgt - N2.lft ? N2.suff : N2.suff + N1.suff);
}

void update2(int x, int i) {
    node& N = sgt2[x];
    if (N.rgt - N.lft == 1) {
        N.pref = N.lng = N.suff = 1;
        return;
    }
    (i < N.mid ? update2(2 * x, i) : update2(2 * x + 1, i));
    node& N1 = sgt2[2 * x];
    node& N2 = sgt2[2 * x + 1];
    N.pref = (N1.pref < N1.rgt - N1.lft ? N1.pref : N1.pref + N2.pref);
    N.lng = max(N1.suff + N2.pref, max(N1.lng, N2.lng));
    N.suff = (N2.suff < N2.rgt - N2.lft ? N2.suff : N2.suff + N1.suff);
}

int main()
{
    cin >> n >> m;
    U.resize(n + m);
    for (int i = 0; i < n; i++) {
        cin >> U[i].val;
        U[i].ab = 1;
        U[i].ind = i;
    }
    for (int i = n; i < n + m; i++) {
        cin >> U[i].val;
        U[i].ab = 2;
        U[i].ind = i - n;
    }
    sort(U.begin(), U.end(), smaller);
    build1(1, 0, n);
    build2(1, 0, m);
    for (upd& u : U) {
        (u.ab == 1 ? update1(1, u.ind) : update2(1, u.ind));
        ans = max(ans, sgt1[1].lng * sgt2[1].lng);
        //cout << u.ab << " " << u.val << " " << u.ind << "  " << sgt1[1].lng << " " << sgt2[1].lng << endl;
    }
    cout << ans;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted28ms64376 KiB
2Accepted46ms64916 KiB
subtask214/14
3Accepted23ms64868 KiB
4Accepted21ms65080 KiB
5Accepted21ms65292 KiB
6Accepted28ms65288 KiB
7Accepted28ms65260 KiB
8Accepted28ms65780 KiB
subtask327/27
9Accepted26ms65944 KiB
10Accepted25ms66048 KiB
11Accepted30ms65960 KiB
12Accepted30ms65984 KiB
13Accepted28ms66076 KiB
14Accepted29ms66172 KiB
15Accepted29ms66184 KiB
16Accepted30ms66312 KiB
17Accepted30ms66420 KiB
subtask421/21
18Accepted210ms71008 KiB
19Accepted199ms71096 KiB
20Accepted172ms71076 KiB
21Accepted179ms71076 KiB
22Accepted158ms70428 KiB
23Accepted143ms70680 KiB
24Accepted25ms67052 KiB
subtask538/38
25Accepted263ms71644 KiB
26Accepted268ms71748 KiB
27Accepted246ms71732 KiB
28Accepted246ms71856 KiB
29Accepted231ms72068 KiB
30Accepted231ms72132 KiB
31Accepted200ms72136 KiB
32Accepted170ms70448 KiB
33Accepted170ms70448 KiB
34Accepted129ms70448 KiB
35Accepted142ms70456 KiB
36Accepted222ms72144 KiB
37Accepted218ms72248 KiB
38Accepted230ms72360 KiB
39Accepted246ms72348 KiB
40Accepted252ms72320 KiB
41Accepted212ms71536 KiB
42Accepted206ms72072 KiB
43Accepted202ms72172 KiB
44Accepted226ms72200 KiB