oj.uz

Submission #511623

# Submission time Handle Problem Language Result Execution time Memory
511623 2022-01-16T03:17:33 Z KoD 3D Histogram (COCI20_histogram) C++17
110 / 110
 1626 ms 140636 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1624 KB Output is correct
2 Correct 8 ms 1668 KB Output is correct
3 Correct 7 ms 1660 KB Output is correct
4 Correct 7 ms 1660 KB Output is correct
5 Correct 7 ms 1580 KB Output is correct
6 Correct 8 ms 1632 KB Output is correct
7 Correct 7 ms 1596 KB Output is correct
8 Correct 7 ms 1620 KB Output is correct
9 Correct 7 ms 1632 KB Output is correct
10 Correct 7 ms 1660 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 7 ms 1724 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1624 KB Output is correct
2 Correct 8 ms 1668 KB Output is correct
3 Correct 7 ms 1660 KB Output is correct
4 Correct 7 ms 1660 KB Output is correct
5 Correct 7 ms 1580 KB Output is correct
6 Correct 8 ms 1632 KB Output is correct
7 Correct 7 ms 1596 KB Output is correct
8 Correct 7 ms 1620 KB Output is correct
9 Correct 7 ms 1632 KB Output is correct
10 Correct 7 ms 1660 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 7 ms 1724 KB Output is correct
13 Correct 1450 ms 138240 KB Output is correct
14 Correct 1428 ms 140636 KB Output is correct
15 Correct 1483 ms 138980 KB Output is correct
16 Correct 1493 ms 138956 KB Output is correct
17 Correct 1511 ms 140444 KB Output is correct
18 Correct 1626 ms 140532 KB Output is correct
19 Correct 1490 ms 140188 KB Output is correct
20 Correct 1481 ms 140500 KB Output is correct
21 Correct 1395 ms 139572 KB Output is correct
22 Correct 1356 ms 140124 KB Output is correct
23 Correct 109 ms 14172 KB Output is correct
24 Correct 1596 ms 138568 KB Output is correct