31542023-02-20 22:37:49zsomborMágikus táblázatcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva28ms64376 KiB
2Elfogadva46ms64916 KiB
subtask214/14
3Elfogadva23ms64868 KiB
4Elfogadva21ms65080 KiB
5Elfogadva21ms65292 KiB
6Elfogadva28ms65288 KiB
7Elfogadva28ms65260 KiB
8Elfogadva28ms65780 KiB
subtask327/27
9Elfogadva26ms65944 KiB
10Elfogadva25ms66048 KiB
11Elfogadva30ms65960 KiB
12Elfogadva30ms65984 KiB
13Elfogadva28ms66076 KiB
14Elfogadva29ms66172 KiB
15Elfogadva29ms66184 KiB
16Elfogadva30ms66312 KiB
17Elfogadva30ms66420 KiB
subtask421/21
18Elfogadva210ms71008 KiB
19Elfogadva199ms71096 KiB
20Elfogadva172ms71076 KiB
21Elfogadva179ms71076 KiB
22Elfogadva158ms70428 KiB
23Elfogadva143ms70680 KiB
24Elfogadva25ms67052 KiB
subtask538/38
25Elfogadva263ms71644 KiB
26Elfogadva268ms71748 KiB
27Elfogadva246ms71732 KiB
28Elfogadva246ms71856 KiB
29Elfogadva231ms72068 KiB
30Elfogadva231ms72132 KiB
31Elfogadva200ms72136 KiB
32Elfogadva170ms70448 KiB
33Elfogadva170ms70448 KiB
34Elfogadva129ms70448 KiB
35Elfogadva142ms70456 KiB
36Elfogadva222ms72144 KiB
37Elfogadva218ms72248 KiB
38Elfogadva230ms72360 KiB
39Elfogadva246ms72348 KiB
40Elfogadva252ms72320 KiB
41Elfogadva212ms71536 KiB
42Elfogadva206ms72072 KiB
43Elfogadva202ms72172 KiB
44Elfogadva226ms72200 KiB