oj.uz

Submission #484927

# Submission time Handle Problem Language Result Execution time Memory
484927 2021-11-05T18:07:10 Z Kirill22 3D Histogram (COCI20_histogram) C++17
110 / 110
 1182 ms 48832 KB 
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int) (x).size()
#define ld long double

struct line {
    long long k, b;
    line() {}
    line(long long k, long long b) : k(k), b(b) {}
};

ld X(line a, line b) {
    return ((ld) a.b - b.b) / ((ld) b.k - a.k);
}

bool cmp(line x, line y) {
    if (x.k == y.k) return x.b > y.b;
    return x.k < y.k;
}

struct kht {
    vector<line> st;
    int id = 0;
    kht() {}

    void build(vector<line>& t) {
        for (int i = 0; i < sz(t); i++) {
            if (i && t[i - 1].k == t[i].k) continue;
            while (sz(st) >= 2) {
                line x = st.back();
                st.pop_back();
                line y = st.back();
                if (X(x, y) <= X(x, t[i])) {
                    st.push_back(x);
                    break;
                }
            }
            st.push_back(t[i]);
        }
    }

    long long get(int x) {
        while (id + 1 < sz(st) && X(st[id], st[id + 1]) <= x) id++;
        while (id - 1 >= 0 && X(st[id], st[id - 1]) >= x) id--;
        return x * st[id].k + st[id].b;
    }

    void clear() {
        id = 0;
        st.clear();
    }
};

const int N = 200000;

kht tree[4 * N];
pii a[N], dp[N];
long long ans = 0;

void chill(vector<pii>& res, int mid) {
    int n = sz(res);
    for (int i = mid; i >= 0; i--) {
        while (mid + 1 < n && res[mid + 1].fi >= res[i].fi && res[mid + 1].se >= res[i].se) {
            mid++;
        }
        ans = max(ans, 1ll * res[i].fi * res[i].se * (mid - i + 1));
    }
}

void build(int v, int l, int r, vector<pii>& res) {
    vector<line> a;
    if (l + 1 == r) {
        tree[v].clear();
        a = {line(-res[l].se, 1ll * res[l].se * (l + 1))};
        tree[v].build(a);
        return;
    }
    int m = (l + r) / 2;
    build(v * 2 + 1, l, m, res);
    build(v * 2 + 2, m, r, res);
    int i = 0, j = 0;
    while (i < sz(tree[v * 2 + 1].st) || j < sz(tree[v * 2 + 2].st)) {
        if (j == sz(tree[v * 2 + 2].st) || (i != sz(tree[v * 2 + 1].st) &&
        cmp(tree[v * 2 + 1].st[i], tree[v * 2 + 2].st[j]))) {
            a.push_back(tree[v * 2 + 1].st[i++]);
        }
        else {
            a.push_back(tree[v * 2 + 2].st[j++]);
        }
    }
    tree[v].clear();
    tree[v].build(a);
}

void get(int v, int l, int r, int l1, int r1, int L, int x) {
    if (l1 >= r || l >= r1) return;
    if (l1 <= l && r <= r1) {
        ans = max(ans, 1ll * tree[v].get(L) * x);
        return;
    }
    int m = (l + r) / 2;
    get(v * 2 + 1, l, m, l1, r1, L, x);
    get(v * 2 + 2, m, r, l1, r1, L, x);
}

void flex(vector<pii>& res, int mid) {
    int n = sz(res);
    vector<pii> query(n);
    int id = mid, id2 = mid;
    for (int i = mid; i >= 0; i--) {
        while (id + 1 < n && res[id + 1].fi >= res[i].fi) {
            id++;
        }
        query[i].se = id;
        while (id2 < n && res[id2].se > res[i].se) {
            id2++;
        }
        query[i].fi = id2;
    }
    build(0, 0, n, res);
    for (int i = 0; i <= mid; i++) {
        get(0, 0, n, query[i].fi, query[i].se + 1, i, res[i].fi);
    }
}

void solve(int l, int r) {
    if (l > r) return;
    int m = (l + r) / 2;
    solve(l, m - 1);
    solve(m + 1, r);
    dp[m] = a[m];
    for (int i = m + 1; i <= r; i++) {
        dp[i] = {min(dp[i - 1].fi, a[i].fi), min(dp[i - 1].se, a[i].se)};
    }
    for (int i = m - 1; i >= l; i--) {
        dp[i] = {min(dp[i + 1].fi, a[i].fi), min(dp[i + 1].se, a[i].se)};
    }
    vector<pii> res;
    for (int i = l; i <= r; i++) {
        res.push_back(dp[i]);
    }
    int pos = m - l;
    chill(res, pos);
    flex(res, pos);
    reverse(all(res));
    pos = sz(res) - pos - 1;
    chill(res, pos);
    flex(res, pos);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].fi >> a[i].se;
    }
    solve(0, n - 1);
    cout << ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 25548 KB Output is correct
2 Correct 26 ms 25604 KB Output is correct
3 Correct 18 ms 25548 KB Output is correct
4 Correct 21 ms 25548 KB Output is correct
5 Correct 28 ms 25548 KB Output is correct
6 Correct 25 ms 25456 KB Output is correct
7 Correct 20 ms 25552 KB Output is correct
8 Correct 20 ms 25548 KB Output is correct
9 Correct 19 ms 25568 KB Output is correct
10 Correct 30 ms 25548 KB Output is correct
11 Correct 17 ms 25284 KB Output is correct
12 Correct 20 ms 25576 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 25548 KB Output is correct
2 Correct 26 ms 25604 KB Output is correct
3 Correct 18 ms 25548 KB Output is correct
4 Correct 21 ms 25548 KB Output is correct
5 Correct 28 ms 25548 KB Output is correct
6 Correct 25 ms 25456 KB Output is correct
7 Correct 20 ms 25552 KB Output is correct
8 Correct 20 ms 25548 KB Output is correct
9 Correct 19 ms 25568 KB Output is correct
10 Correct 30 ms 25548 KB Output is correct
11 Correct 17 ms 25284 KB Output is correct
12 Correct 20 ms 25576 KB Output is correct
13 Correct 1072 ms 44148 KB Output is correct
14 Correct 1139 ms 47832 KB Output is correct
15 Correct 944 ms 44440 KB Output is correct
16 Correct 964 ms 44392 KB Output is correct
17 Correct 1097 ms 46780 KB Output is correct
18 Correct 1168 ms 48240 KB Output is correct
19 Correct 1113 ms 47052 KB Output is correct
20 Correct 1176 ms 48240 KB Output is correct
21 Correct 967 ms 44180 KB Output is correct
22 Correct 1182 ms 48832 KB Output is correct
23 Correct 90 ms 27204 KB Output is correct
24 Correct 967 ms 44156 KB Output is correct