Submission #511623

#	Time	Username	Problem	Language	Result	Execution time	Memory
511623		KoD	3D Histogram (COCI20_histogram)	C++17	110 / 110	1626 ms	140636 KiB

histogram

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using i64 = std::int64_t;

template <class F> struct RecLambda : private F {
    explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

void setmax(i64& x, const i64 y) {
    if (x < y) {
        x = y;
    }
}

struct Line {
    i64 a, b;
    i64 eval(const i64 x) const { 
        return a * x + b; 
    }
};

i64 rem_euclid(i64 a, const i64 b) {
    a %= b;
    return a < 0 ? a + b : a;
}

i64 floor_div(const i64 a, const i64 b) {
    return (a - rem_euclid(a, b)) / b;
}

i64 ceil_div(const i64 a, const i64 b) {
    return floor_div(a + b - 1, b);
}

struct CHT {
    std::deque<Line> line;
    CHT() : line() {}
    i64 change(const Line& l, const Line& m) {
        return ceil_div(m.b - l.b, l.a - m.a);
    }
    void add(const Line& l) {
        int n = line.size();
        if (n > 0 and line[n - 1].a == l.a) {
            return;
        }
        while (n >= 2) {
            if (change(line[n - 2], line[n - 1]) < change(line[n - 1], l)) {
                break;
            }
            line.pop_back();
            n -= 1;
        }
        line.push_back(l);
    }
    i64 max(const i64 x) {
        int n = line.size();
        if (n == 0) {
            return 0;
        }
        while (n >= 2 and line[0].eval(x) <= line[1].eval(x)) {
            line.pop_front();
            n -= 1;
        }
        return line[0].eval(x);
    }
};

struct Segtree {
    int size;
    vector<CHT> data;
    Segtree(const int n) : size(n), data(2 * n) {}
    void add(int k, const Line& l) {
        k += size;
        while (k > 0) {
            data[k].add(l);
            k >>= 1;
        }
    }
    i64 max(int l, int r, const i64 x) {
        l += size, r += size;
        i64 ret = 0;
        while (l < r) {
            if (l & 1) {
                setmax(ret, data[l].max(x));
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                setmax(ret, data[r].max(x));
            }
            l >>= 1, r >>= 1;
        }
        return ret;
    }
};

i64 solve(const int n, const vector<int>& x1, const vector<int>& y1, const int m, const vector<int>& x2, const vector<int>& y2) {
    Segtree seg(m);
    for (int i = m - 1; i >= 0; --i) {
        seg.add(i, Line{y2[i], (i64)y2[i] * (i + 1)});
    }
    int j = 0, k = 0;
    i64 ret = 0;
    for (int i = 0; i < n; ++i) {
        while (j < m and x1[i] <= x2[j]) {
            j += 1;
        }
        while (k < j and y1[i] < y2[k]) {
            k += 1;
        }
        if (k != 0) {
            setmax(ret, (i64)x1[i] * y1[i] * (i + 1 + k));
        }
        if (k != j) {
            setmax(ret, (i64)x1[i] * seg.max(k, j, i + 1));
        }
    }
    return ret;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<int> A(N), B(N);
    i64 ans = 0;
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i] >> B[i];
        setmax(ans, (i64)A[i] * B[i]);
    }
    RecLambda([&](auto&& dfs, const int left, const int right) -> void {
        if (right - left <= 1) return;
        const int mid = (left + right) / 2;
        dfs(left, mid);
        dfs(mid, right);
        const int lsize = mid - left, rsize = right - mid;
        vector<int> x1(lsize), y1(lsize), x2(rsize), y2(rsize);
        for (int i = mid - 1, a = 1000000, b = 1000000; i >= left; --i) {
            a = std::min(a, A[i]);
            b = std::min(b, B[i]);
            setmax(ans, (i64)a * b * (mid - i));
            x1[mid - i - 1] = a, y1[mid - i - 1] = b;
        }
        for (int i = mid, a = 1000000, b = 1000000; i < right; ++i) {
            a = std::min(a, A[i]);
            b = std::min(b, B[i]);
            setmax(ans, (i64)a * b * (i - mid + 1));
            x2[i - mid] = a, y2[i - mid] = b;
        }
        setmax(ans, solve(lsize, x1, y1, rsize, x2, y2));
        setmax(ans, solve(rsize, x2, y2, lsize, x1, y1));
    })(0, N);
    std::cout << ans << '\n';
    return 0;
}

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