Submission #484927

#	Time	Username	Problem	Language	Result	Execution time	Memory
484927		Kirill22	3D Histogram (COCI20_histogram)	C++17	110 / 110	1182 ms	48832 KiB

histogram

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int) (x).size()
#define ld long double

struct line {
    long long k, b;
    line() {}
    line(long long k, long long b) : k(k), b(b) {}
};

ld X(line a, line b) {
    return ((ld) a.b - b.b) / ((ld) b.k - a.k);
}

bool cmp(line x, line y) {
    if (x.k == y.k) return x.b > y.b;
    return x.k < y.k;
}

struct kht {
    vector<line> st;
    int id = 0;
    kht() {}

    void build(vector<line>& t) {
        for (int i = 0; i < sz(t); i++) {
            if (i && t[i - 1].k == t[i].k) continue;
            while (sz(st) >= 2) {
                line x = st.back();
                st.pop_back();
                line y = st.back();
                if (X(x, y) <= X(x, t[i])) {
                    st.push_back(x);
                    break;
                }
            }
            st.push_back(t[i]);
        }
    }

    long long get(int x) {
        while (id + 1 < sz(st) && X(st[id], st[id + 1]) <= x) id++;
        while (id - 1 >= 0 && X(st[id], st[id - 1]) >= x) id--;
        return x * st[id].k + st[id].b;
    }

    void clear() {
        id = 0;
        st.clear();
    }
};

const int N = 200000;

kht tree[4 * N];
pii a[N], dp[N];
long long ans = 0;

void chill(vector<pii>& res, int mid) {
    int n = sz(res);
    for (int i = mid; i >= 0; i--) {
        while (mid + 1 < n && res[mid + 1].fi >= res[i].fi && res[mid + 1].se >= res[i].se) {
            mid++;
        }
        ans = max(ans, 1ll * res[i].fi * res[i].se * (mid - i + 1));
    }
}

void build(int v, int l, int r, vector<pii>& res) {
    vector<line> a;
    if (l + 1 == r) {
        tree[v].clear();
        a = {line(-res[l].se, 1ll * res[l].se * (l + 1))};
        tree[v].build(a);
        return;
    }
    int m = (l + r) / 2;
    build(v * 2 + 1, l, m, res);
    build(v * 2 + 2, m, r, res);
    int i = 0, j = 0;
    while (i < sz(tree[v * 2 + 1].st) || j < sz(tree[v * 2 + 2].st)) {
        if (j == sz(tree[v * 2 + 2].st) || (i != sz(tree[v * 2 + 1].st) &&
        cmp(tree[v * 2 + 1].st[i], tree[v * 2 + 2].st[j]))) {
            a.push_back(tree[v * 2 + 1].st[i++]);
        }
        else {
            a.push_back(tree[v * 2 + 2].st[j++]);
        }
    }
    tree[v].clear();
    tree[v].build(a);
}

void get(int v, int l, int r, int l1, int r1, int L, int x) {
    if (l1 >= r || l >= r1) return;
    if (l1 <= l && r <= r1) {
        ans = max(ans, 1ll * tree[v].get(L) * x);
        return;
    }
    int m = (l + r) / 2;
    get(v * 2 + 1, l, m, l1, r1, L, x);
    get(v * 2 + 2, m, r, l1, r1, L, x);
}

void flex(vector<pii>& res, int mid) {
    int n = sz(res);
    vector<pii> query(n);
    int id = mid, id2 = mid;
    for (int i = mid; i >= 0; i--) {
        while (id + 1 < n && res[id + 1].fi >= res[i].fi) {
            id++;
        }
        query[i].se = id;
        while (id2 < n && res[id2].se > res[i].se) {
            id2++;
        }
        query[i].fi = id2;
    }
    build(0, 0, n, res);
    for (int i = 0; i <= mid; i++) {
        get(0, 0, n, query[i].fi, query[i].se + 1, i, res[i].fi);
    }
}

void solve(int l, int r) {
    if (l > r) return;
    int m = (l + r) / 2;
    solve(l, m - 1);
    solve(m + 1, r);
    dp[m] = a[m];
    for (int i = m + 1; i <= r; i++) {
        dp[i] = {min(dp[i - 1].fi, a[i].fi), min(dp[i - 1].se, a[i].se)};
    }
    for (int i = m - 1; i >= l; i--) {
        dp[i] = {min(dp[i + 1].fi, a[i].fi), min(dp[i + 1].se, a[i].se)};
    }
    vector<pii> res;
    for (int i = l; i <= r; i++) {
        res.push_back(dp[i]);
    }
    int pos = m - l;
    chill(res, pos);
    flex(res, pos);
    reverse(all(res));
    pos = sz(res) - pos - 1;
    chill(res, pos);
    flex(res, pos);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].fi >> a[i].se;
    }
    solve(0, n - 1);
    cout << ans;
}

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