Submission #781270

#	Time	Username	Problem	Language	Result	Execution time	Memory
781270		PurpleCrayon	3D Histogram (COCI20_histogram)	C++17	0 / 110	6 ms	1124 KiB

histogram

#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 2e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;
using D = long double;

struct Line {
    ll m, b;
    ll eval(ll x) {
        return m * x + b;
    }

    D isect(Line l) {
        return ((D) l.b - b) / (m - l.m);
    }
};

struct Hull {
    // add line a * x + b
    // query max at point x
    // slopes are decreasing, query points are increasing
    deque<Line> dq;
    void add(Line l) {
        while (sz(dq) >= 2 && dq[0].isect(dq[1]) >= dq[1].isect(l)) {
            dq.pop_front();
        }

        dq.push_back(l);
    }

    ll qry(ll x) {
        if (!sz(dq)) return INF;
        while (sz(dq) >= 2 && dq[0].isect(dq[1]) < x)
            dq.pop_front();

        return dq[0].eval(x);
    }
};

int n;
ll a[N], b[N];
ll ans = 0;

void f(vector<pair<ll, ll>> one, vector<pair<ll, ll>> two) {
    // assume min of first is on one's side
    // both one and two are decreasing

    int m = sz(two);
    vector<Hull> bit(m);
    auto add = [&](int p, Line l) {
        p = m - 1 - p;
        for (int i = p; i < m; i |= i+1)
            bit[i].add(l);
    };

    auto qry = [&](int p, ll x) {
        p = m - 1 - p; // <= p
        ll ret = 0;
        for (int i = p+1; i > 0; i &= i-1)
            ret = max(ret, bit[i-1].qry(x));

        return ret;
    };

    int p1 = 0;
    int p2 = 0;
    int cnt_me = 0;
    for (pair<ll, ll> x : one) {
        while (p1 < sz(two) && two[p1].first >= x.first && two[p1].second >= x.second) {
            p1++;
        }

        while (p2 < sz(two) && two[p2].first >= x.first) {
            add(p2, {two[p2].second, two[p2].second * (p2 + 1)});
            p2++;
        }

        cnt_me++;
        ans = max(ans, x.first * x.second * (cnt_me + p1));

        ll best = qry(p1, cnt_me);
        if (best < INF)
            ans = max(ans, x.first * best);

        // [p1, p2)
        // x.first * he.second * (cnt_me + cnt_he)
        // he.second * cnt_me + he.second * cnt_he
    }
}

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

    int m = (l + r) / 2;
    rec(l, m), rec(m+1, r);

    vector<pair<ll, ll>> one, two;
    ll ma1 = MOD, mb1 = MOD;
    for (int i = m+1; i <= r; i++) {
        ma1 = min(ma1, a[i]);
        mb1 = min(mb1, b[i]);

        one.emplace_back(ma1, mb1);
    }

    ll ma2 = MOD, mb2 = MOD;
    for (int i = m; i >= l; i--) {
        ma2 = min(ma2, a[i]);
        mb2 = min(mb2, b[i]);

        two.emplace_back(ma2, mb2);
    }

    f(one, two), f(two, one);
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
    rec(0, n-1);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

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