Submission #369316

#	Time	Username	Problem	Language	Result	Execution time	Memory
369316		kartel	3D Histogram (COCI20_histogram)	C++14	110 / 110	392 ms	30576 KiB

histogram

#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <ll, ll>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long double ld;
typedef unsigned long long ull;
typedef short int si;

const int N = 2e5 + 500;
const int MS = 1e6;

ll sfa[N], sfb[N], pra[N], prb[N], a[N], b[N];
ll ans;
int n;

int root[4 * N];
ll lst[MS], cr[MS];
pair <ll, ll> ln[MS];
int siz;

int add(ll k, ll b) {
    int v = siz++;
    ln[v] = {k, b};

    return siz - 1;
}

ll cross(ll k, ll b, ll k1, ll b1) {
    return ((b - b1) / (k1 - k) + !!((b - b1) % (k1 - k)));
}

void build(int v, int l, int r) {
    int i = l;
    while (i <= r && prb[l] == prb[i])
        i++;

    root[v] = add(-prb[i - 1], prb[i - 1] * i);
    lst[root[v]] = root[v];
    cr[root[v]] = -1e18;

    int last = root[v];

    for (; i <= r;) {
        int j = i;
        while (i <= r && prb[i] == prb[j])
            i++;

        ll k = -prb[i - 1], b = prb[i - 1] * i;
        ll crp;

        while (1) {
            crp = cross(k, b, ln[last].F, ln[last].S);

            if (crp > cr[last])
                break;

            last = lst[last];
        }

        root[v] = add(k, b);
        lst[root[v]] = last;
        cr[root[v]] = crp;
        last = root[v];
    }

    if (l == r)
        return;

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

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

void upd_a(ll vl) {
    ans = max(ans, vl);
}

ll get(int v, int l, int r, int tl, int tr, int X) {
    if (l > r || tl > tr || tl > r || l > tr)
        return -1e18;

    if (l == tl && r == tr) {
        while (cr[root[v]] > X)
            root[v] = lst[root[v]];

        return ln[root[v]].F * X + ln[root[v]].S;
    }

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

    return max(get(v * 2, l, md, tl, min(md, tr), X),
               get(v * 2 + 1, md + 1, r, max(md + 1, tl), tr, X));
}

void solve(int le, int ri) {
    if (le > ri)
        return;

    if (le == ri) {
        upd_a(a[le] * b[le]);
        return;
    }

    int md = (le + ri) >> 1;

    /// f -> [le, md], g -> [le, md]
    pra[md] = prb[md] = 1e9;
    for (int i = md + 1; i <= ri; i++) {
        pra[i] = min(pra[i - 1], a[i]);
        prb[i] = min(prb[i - 1], b[i]);
    }

    ll r = md + 1, f = 1e9, g = 1e9;

    for (int l = md; l >= le; l--) {
        f = min(f, a[l]);
        g = min(g, b[l]);
        while (r <= ri && pra[r] >= f && prb[r] >= g)
            r++;

        upd_a((r - l) * 1ll * f * g);
    }

    ///f -> [md, ri], g -> [md; ri]

    sfa[md] = sfb[md] = 1e9;
    for (int l = md - 1; l >= le; l--) {
        sfa[l] = min(sfa[l + 1], a[l]);
        sfb[l] = min(sfb[l + 1], b[l]);
    }

    int l = md - 1;
    f = 1e9, g = 1e9;

    for (int r = md; r <= ri; r++) {
        f = min(f, a[r]);
        g = min(g, b[r]);
        while (l >= le && sfa[l] >= f && sfb[l] >= g)
            l--;

        upd_a((r - l) * 1ll * f * g);
    }

    /// f -> [le, md], g -> [md + 1, ri]

    siz = 0;

    build(1, md + 1, ri);

    f = 1e9, g = 1e9;
    r = md + 1;
    int r1 = md + 1;

    for (int l = md; l >= le; l--) {
        f = min(f, a[l]);
        g = min(g, b[l]);

        while (r <= ri && g < prb[r])
            r++;

        while (r1 <= ri && f <= pra[r1])
            r1++;

        if (r <= r1 - 1) {
            ll cur = get(1, md + 1, ri, r, r1 - 1, l);

//            cerr << f * cur << el;

            if (cur != -1e18) {
                upd_a(f * 1ll * cur);
            }
        }
    }

    /// g -> [le, md], f -> [md + 1, ri]

    siz = 0;

    for (int i = md + 1; i <= ri; i++) {
        swap(pra[i], prb[i]);
    }

    build(1, md + 1, ri);

    f = 1e9, g = 1e9;
    r = md + 1;
    r1 = md + 1;

    for (int l = md; l >= le; l--) {
        f = min(f, a[l]);
        g = min(g, b[l]);

        while (r <= ri && g <= pra[r])
            r++;

        while (r1 <= ri && f < prb[r1])
            r1++;

        if (r1 <= r - 1) {
            ll cur = get(1, md + 1, ri, r1, r - 1, l);

            if (cur != -1e18) {
                upd_a(g * 1ll * cur);
            }
        }
    }

    //806801766313992
    //1675888823757

    solve(le, md - 1);
    solve(md + 1, ri);
}

int main()
{
//    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	in("game.in");
//	out("game.out");
//    in("input.txt");
//    out("output.txt");

//    clock_t tStart = clock();

    cin >> n;

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

    solve(1, n);

    cout << ans;
}


/*

7
4 6 7 2 3 1 5
*/

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