oj.uz

Submission #576093

# Submission time Handle Problem Language Result Execution time Memory
576093 2022-06-12T10:03:28 Z eecs 3D Histogram (COCI20_histogram) C++17
110 / 110
 833 ms 64420 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200010;
int n, a[maxn], b[maxn];
long long y[maxn], res[maxn];
vector<array<int, 2>> Q[maxn << 2];

#define mid ((l + r) >> 1)
#define ls (k << 1)
#define rs (k << 1 | 1)
void ins(int k, int l, int r, int ql, int qr, array<int, 2> v) {
    if (l >= ql && r <= qr) return Q[k].push_back(v);
    if (mid >= ql) ins(ls, l, mid, ql, qr, v);
    if (mid < qr) ins(rs, mid + 1, r, ql, qr, v);
}

vector<int> calc(int k, int l, int r) {
    vector<int> V, st;
    if (l == r) {
        V = {l};
    } else {
        auto L = calc(ls, l, mid), R = calc(rs, mid + 1, r);
        V.resize(L.size() + R.size());
        merge(L.begin(), L.end(), R.begin(), R.end(), V.begin(), [&](int i, int j) { return b[i] < b[j]; });
    }
    auto ccw = [&](int i, int j, int k) {
        return (b[j] - b[i]) * (y[k] - y[j]) >= (b[k] - b[j]) * (y[j] - y[i]);
    };
    for (int i : V) {
        if (!st.empty() && b[i] == b[st.back()] && y[i] <= y[st.back()]) continue;
        while (st.size() > 1 && ccw(st[st.size() - 2], st.back(), i)) st.pop_back();
        st.push_back(i);
    }
    for (int i = 0, j = 0; i < Q[k].size(); i++) {
        auto eval = [&](int j) { return 1LL * Q[k][i][0] * b[st[j]] + y[st[j]]; };
        while (j + 1 < st.size() && eval(j) < eval(j + 1)) j++;
        res[Q[k][i][1]] = max(res[Q[k][i][1]], eval(j));
    }
    return st;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
    long long ans = 0;
    auto solve = [&](auto self, int l, int r) {
        if (l == r) { ans = max(ans, 1LL * a[l] * b[l]); return; }
        self(self, l, mid), self(self, mid + 1, r);
        vector<int> _a(a + l, a + r + 1), _b(b + l, b + r + 1);
        for (int i = mid - 1; i >= l; i--) {
            a[i] = min(a[i], a[i + 1]), b[i] = min(b[i], b[i + 1]);
        }
        for (int i = mid + 2; i <= r; i++) {
            a[i] = min(a[i], a[i - 1]), b[i] = min(b[i], b[i - 1]);
        }
        fill(res + l, res + r + 1, -1e12);
        fill(Q, Q + (r - l + 1) * 2, vector<array<int, 2>>());
        for (int i = l; i <= r; i++) {
            y[i] = 1LL * b[i] * (i <= mid ? 1 - i : 1 + i);
        }
        for (int i = mid, j = mid, k = mid; i >= l; i--) {
            while (j < r && a[i] <= a[j + 1]) j++;
            while (k < r && b[i] <= b[k + 1]) k++;
            int t = min(j, k);
            if (t > mid) ans = max(ans, 1LL * a[i] * b[i] * (t - i + 1));
            if (k < j) ins(1, mid + 1, r, k + 1, j, {-i, i});
        }
        calc(1, mid + 1, r);
        fill(Q, Q + (r - l + 1) * 2, vector<array<int, 2>>());
        for (int i = mid + 1, j = mid + 1, k = mid + 1; i <= r; i++) {
            while (j > l && a[i] <= a[j - 1]) j--;
            while (k > l && b[i] <= b[k - 1]) k--;
            int t = max(j, k);
            if (t <= mid) ans = max(ans, 1LL * a[i] * b[i] * (i - t + 1));
            if (j < k) ins(1, l, mid, j, k - 1, {i, i});
        }
        calc(1, l, mid);
        for (int i = l; i <= r; i++) {
            ans = max(ans, a[i] * res[i]);
        }
        copy(_a.begin(), _a.end(), a + l);
        copy(_b.begin(), _b.end(), b + l);
    };
    solve(solve, 1, n);
    cout << ans << "\n";
    return 0;
}

Compilation message

histogram.cpp: In function 'std::vector<int> calc(int, int, int)':
histogram.cpp:35:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0, j = 0; i < Q[k].size(); i++) {
      |                            ~~^~~~~~~~~~~~~
histogram.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         while (j + 1 < st.size() && eval(j) < eval(j + 1)) j++;
      |                ~~~~~~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19412 KB Output is correct
2 Correct 15 ms 19260 KB Output is correct
3 Correct 14 ms 19156 KB Output is correct
4 Correct 16 ms 19256 KB Output is correct
5 Correct 15 ms 19284 KB Output is correct
6 Correct 17 ms 19412 KB Output is correct
7 Correct 15 ms 19136 KB Output is correct
8 Correct 18 ms 19204 KB Output is correct
9 Correct 15 ms 19284 KB Output is correct
10 Correct 16 ms 19256 KB Output is correct
11 Correct 12 ms 19136 KB Output is correct
12 Correct 15 ms 19284 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19412 KB Output is correct
2 Correct 15 ms 19260 KB Output is correct
3 Correct 14 ms 19156 KB Output is correct
4 Correct 16 ms 19256 KB Output is correct
5 Correct 15 ms 19284 KB Output is correct
6 Correct 17 ms 19412 KB Output is correct
7 Correct 15 ms 19136 KB Output is correct
8 Correct 18 ms 19204 KB Output is correct
9 Correct 15 ms 19284 KB Output is correct
10 Correct 16 ms 19256 KB Output is correct
11 Correct 12 ms 19136 KB Output is correct
12 Correct 15 ms 19284 KB Output is correct
13 Correct 794 ms 64420 KB Output is correct
14 Correct 728 ms 30628 KB Output is correct
15 Correct 678 ms 37828 KB Output is correct
16 Correct 746 ms 46916 KB Output is correct
17 Correct 802 ms 36624 KB Output is correct
18 Correct 720 ms 54884 KB Output is correct
19 Correct 696 ms 50368 KB Output is correct
20 Correct 728 ms 56108 KB Output is correct
21 Correct 738 ms 43940 KB Output is correct
22 Correct 833 ms 49936 KB Output is correct
23 Correct 76 ms 23492 KB Output is correct
24 Correct 638 ms 28456 KB Output is correct