제출 #576093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
576093		eecs	3D Histogram (COCI20_histogram)	C++17	110 / 110	833 ms	64420 KiB

histogram

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 20
• Subtask 2: 90 / 90