oj.uz

Submission #781298

# Submission time Handle Problem Language Result Execution time Memory
781298 2023-07-13T02:14:58 Z PurpleCrayon 3D Histogram (COCI20_histogram) C++17
110 / 110
 1214 ms 135744 KB 
#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) {
        if (sz(dq) && dq[0].b >= l.b) return;
        if (sz(dq) && dq[0].m == l.m) {
            l.m = max(l.m, dq[0].m);
            dq.pop_front();
        }

        while (sz(dq) >= 2 && dq[0].isect(dq[1]) <= dq[1].isect(l)) {
            dq.pop_front();
        }

        dq.push_front(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 > 0)
            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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1464 KB Output is correct
2 Correct 5 ms 1576 KB Output is correct
3 Correct 5 ms 1592 KB Output is correct
4 Correct 5 ms 1592 KB Output is correct
5 Correct 4 ms 1512 KB Output is correct
6 Correct 5 ms 1620 KB Output is correct
7 Correct 4 ms 1492 KB Output is correct
8 Correct 6 ms 1548 KB Output is correct
9 Correct 6 ms 1668 KB Output is correct
10 Correct 7 ms 1612 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 6 ms 1616 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1464 KB Output is correct
2 Correct 5 ms 1576 KB Output is correct
3 Correct 5 ms 1592 KB Output is correct
4 Correct 5 ms 1592 KB Output is correct
5 Correct 4 ms 1512 KB Output is correct
6 Correct 5 ms 1620 KB Output is correct
7 Correct 4 ms 1492 KB Output is correct
8 Correct 6 ms 1548 KB Output is correct
9 Correct 6 ms 1668 KB Output is correct
10 Correct 7 ms 1612 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 6 ms 1616 KB Output is correct
13 Correct 1030 ms 134956 KB Output is correct
14 Correct 840 ms 135096 KB Output is correct
15 Correct 952 ms 133728 KB Output is correct
16 Correct 930 ms 133800 KB Output is correct
17 Correct 759 ms 131996 KB Output is correct
18 Correct 976 ms 135040 KB Output is correct
19 Correct 927 ms 134784 KB Output is correct
20 Correct 921 ms 135144 KB Output is correct
21 Correct 954 ms 134136 KB Output is correct
22 Correct 753 ms 131672 KB Output is correct
23 Correct 65 ms 13648 KB Output is correct
24 Correct 1214 ms 135744 KB Output is correct