Submission #366496

#	Time	Username	Problem	Language	Result	Execution time	Memory
366496		NONAME	3D Histogram (COCI20_histogram)	C++14	20 / 110	2506 ms	7192 KiB

histogram

#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
using namespace std;

const int man = (int)(2e5 + 500);

int n;
int a[man], b[man], t[4 * man];
int lft[man][2], rgt[man][2];

void build(int v, int l, int r) {
    t[v] = 1e9;
    if (l > r) {
        return;
    }
    if (l == r) {
        t[v] = b[l];
        return;
    }

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

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

    t[v] = min(t[v + v], t[v + v + 1]);
}

int get(int v, int l, int r, int ql, int qr) {
    if ((l > qr) || (ql > r)) {
        return 1e9;
    }
    if ((l >= ql) && (r <= qr)) {
        return t[v];
    }

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

    return min(get(v + v, l, md, ql, qr), get(v + v + 1, md + 1, r, ql, qr));
}

void calc(int tp) {
    vector <pair <int, int> > v;
    v.push_back({-1e9, -1});
    for (int i = 0; i < n; ++i) {
        while ((v.back()).first >= a[i]) {
            v.pop_back();
        }
        lft[i][tp] = (v.back()).second;
        v.push_back({a[i], i});
    }
    while (v.empty() == false) {
        v.pop_back();
    }
    v.push_back({-1e9, n});
    for (int i = (n - 1); i >= 0; --i) {
        while ((v.back()).first >= a[i]) {
            v.pop_back();
        }
        rgt[i][tp] = (v.back()).second;
        v.push_back({a[i], i});
    }
}

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

    #ifdef _LOCAL
        in("inC.txt");
        out("outC.txt");
    #endif

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

    for (int tp = 0; tp < 2; ++tp) {
        calc(tp);
        for (int i = 0; i < n; ++i) {
            swap(a[i], b[i]);
        }
    }

    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        int mna = a[i], mnb = b[i];
        for (int j = i; (j < n) && (j - i + 1) <= (int)(6e3); ++j) {
            mna = min(mna, a[j]);
            mnb = min(mnb, b[j]);
            if (((j - i + 1) * 1ll * mna * mnb) > ans) {
                ans = max(ans, (j - i + 1) * 1ll * mna * mnb);
            }
        }
    }

    for (int tp = 0; tp < 2; ++tp) {
        build(1, 0, n - 1);
        for (int i = 0; i < n; ++i) {
            int l = lft[i][tp] + 1, r = rgt[i][tp] - 1;
            int x = get(1, 0, n - 1, l, r);
            ans = max(ans, (r - l + 1) * 1ll * a[i] * x);
        }
        for (int i = 0; i < n; ++i) {
            swap(a[i], b[i]);
        }
    }

    for (int i = 0; i < n; ++i) {
        int l = max(lft[i][0] + 1, lft[i][1] + 1);
        int r = min(rgt[i][0] - 1, rgt[i][1] - 1);

        ans = max(ans, (r - l + 1) * 1ll * a[i] * b[i]);
    }

    cout << ans << "\n";

    return 0;
}

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