Submission #366783

#	Time	Username	Problem	Language	Result	Execution time	Memory
366783		VEGAnn	3D Histogram (COCI20_histogram)	C++14	110 / 110	523 ms	45676 KiB

histogram

#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int N = 200100;
const int BIG = int(4e6);
const int oo = 2e9;
const ll OO = 1e18;
ll B[BIG], ans = 0, FRM[BIG];
int n, a[N], b[N], pref[N], suf[N], pref2[N], suf2[N];
int root[4 * N], ptr[4 * N];
int LST, K[BIG], PRV[BIG];

int NEW(int nk, ll nb, ll wh){
    assert(LST < BIG);

    K[LST] = nk;
    B[LST] = nb;
    FRM[LST] = wh;
    PRV[LST] = -1;

    LST++;

    return LST - 1;
}

ll get_cross_point(int FI, int SE){
    if (K[FI] == K[SE])
        return (B[FI] > B[SE] ? -OO : OO);

    ll BB = B[FI] - B[SE];
    ll KK = K[SE] - K[FI];

    if ((BB >= 0 && KK > 0) || (BB <= 0 && KK < 0))
        return BB / KK + bool(BB % KK);
    else return BB / KK;
}

void build(int v, int l, int r){
    {
        int tit = l;

        while (tit < r && pref2[tit + 1] == pref2[l])
            tit++;

        root[v] = NEW(-pref2[tit], ll(pref2[tit]) * ll(tit), -OO);

        ptr[v] = root[v];

        for (int it = tit + 1; it <= r; it++){
            int cur = NEW(-pref2[it], ll(pref2[it]) * ll(it), -OO);

            while (PRV[ptr[v]] > 0){
                ll CR = get_cross_point(cur, ptr[v]);

                if (CR > FRM[ptr[v]]) break;

                ptr[v] = PRV[ptr[v]];
            }

            PRV[cur] = ptr[v];
            FRM[cur] = get_cross_point(cur, ptr[v]);

            ptr[v] = cur;
        }
    }

    if (l == r) return;

    int md = (l + r) >> 1;

    build(v + v, l, md);
    build(v + v + 1, md + 1, r);
}

//3166121245150

ll get_best(int v, int tl, int tr, int ql, int qr, int X){
    if (ql > qr) return -OO;

    if (tl == ql && qr == tr){
        while (FRM[ptr[v]] > X)
            ptr[v] = PRV[ptr[v]];

        return ll(K[ptr[v]]) * ll(X) + B[ptr[v]];
    }

    int md = (tl + tr) >> 1;

    return max(get_best(v + v, tl, md, ql, min(qr, md), X),
               get_best(v + v + 1, md + 1, tr, max(md + 1, ql), qr, X));
}

void DO_IT(int l, int r){
    for (int i = l; i <= r; i++)
        swap(a[i], b[i]);

    int md = (l + r) >> 1;

    suf[md + 1] = suf2[md + 1] = oo;

    for (int i = md; i >= l; i--) {
        suf[i] = min(suf[i + 1], a[i]);
        suf2[i] = min(suf2[i + 1], b[i]);
    }

    pref[md] = pref2[md] = oo;

    for (int i = md + 1; i <= r; i++) {
        pref[i] = min(pref[i - 1], a[i]);
        pref2[i] = min(pref2[i - 1], b[i]);
    }

    LST = 1;

    build(1, md + 1, r);

    {
        // min_a -- left
        // min_b -- right

        int ptr1 = md, ptr2 = md + 1;

        for (int i = md; i >= l; i--){
            while (ptr1 < r && suf[i] <= pref[ptr1 + 1])
                ptr1++;

            while (ptr2 <= r && suf2[i] < pref2[ptr2])
                ptr2++;

            if (ptr1 >= ptr2)
                ans = max(ans, get_best(1, md + 1, r, ptr2, ptr1, i - 1) * ll(suf[i]));
        }
    }
}

void calc(int l, int r){
    if (l == r) {
        ans = max(ans, ll(a[l]) * ll(b[l]));
        return;
    }

    DO_IT(l, r);
    DO_IT(l, r);

    int md = (l + r) >> 1;

    {
        // min_a -- left
        // min_b -- left

        int ptr1 = md, ptr2 = md;

        for (int i = md; i >= l; i--){
            while (ptr1 < r && suf[i] <= pref[ptr1 + 1])
                ptr1++;

            while (ptr2 < r && suf2[i] <= pref2[ptr2 + 1])
                ptr2++;

            ll MN = min(ptr1, ptr2);

            if (MN > md)
                ans = max(ans, ll(suf[i]) * ll(suf2[i]) * (MN - ll(i) + 1ll));
        }
    }

    {
        // min_a -- right
        // min_b -- right

        int ptr1 = md + 1, ptr2 = md + 1;

        for (int i = md + 1; i <= r; i++){
            while (ptr1 > l && pref[i] <= suf[ptr1 - 1])
                ptr1--;

            while (ptr2 > l && pref2[i] <= suf2[ptr2 - 1])
                ptr2--;

            ll MX = max(ptr1, ptr2);

            if (MX <= md)
                ans = max(ans, ll(pref[i]) * ll(pref2[i]) * (ll(i) - ll(MX) + 1ll));
        }
    }

    calc(l, md);
    calc(md + 1, r);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];

    calc(1, n);

    cout << ans;

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 90 / 90