oj.uz

Submission #366492

# Submission time Handle Problem Language Result Execution time Memory
366492 2021-02-14T09:26:37 Z NONAME 3D Histogram (COCI20_histogram) C++14
20 / 110
 2148 ms 7316 KB 
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
using namespace std;

const int man = (int)(2e5 + 500);

int n;
int a[man], b[man], t[4 * man];
int lft[man][2], rgt[man][2];

void build(int v, int l, int r) {
    t[v] = 1e9;
    if (l > r) {
        return;
    }
    if (l == r) {
        t[v] = b[l];
        return;
    }

    int md = (l + r) >> 1;

    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    t[v] = min(t[v + v], t[v + v + 1]);
}

int get(int v, int l, int r, int ql, int qr) {
    if ((l > qr) || (ql > r)) {
        return 1e9;
    }
    if ((l >= ql) && (r <= qr)) {
        return t[v];
    }

    int md = (l + r) >> 1;

    return min(get(v + v, l, md, ql, qr), get(v + v + 1, md + 1, r, ql, qr));
}

void calc(int tp) {
    vector <pair <int, int> > v;
    v.push_back({-1e9, -1});
    for (int i = 0; i < n; ++i) {
        while ((v.back()).first >= a[i]) {
            v.pop_back();
        }
        lft[i][tp] = (v.back()).second;
        v.push_back({a[i], i});
    }
    while (v.empty() == false) {
        v.pop_back();
    }
    v.push_back({-1e9, n});
    for (int i = (n - 1); i >= 0; --i) {
        while ((v.back()).first >= a[i]) {
            v.pop_back();
        }
        rgt[i][tp] = (v.back()).second;
        v.push_back({a[i], i});
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #ifdef _LOCAL
        in("inC.txt");
        out("outC.txt");
    #endif

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }

    for (int tp = 0; tp < 2; ++tp) {
        calc(tp);
        for (int i = 0; i < n; ++i) {
            swap(a[i], b[i]);
        }
    }

    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        int mna = a[i], mnb = b[i];
        for (int j = i; (j < n) && (j - i + 1) <= (int)(5e3); ++j) {
            mna = min(mna, a[j]);
            mnb = min(mnb, b[j]);
            if (((j - i + 1) * 1ll * mna * mnb) > ans) {
                ans = max(ans, (j - i + 1) * 1ll * mna * mnb);
            }
        }
    }

    for (int tp = 0; tp < 2; ++tp) {
        build(1, 0, n - 1);
        for (int i = 0; i < n; ++i) {
            int l = lft[i][tp] + 1, r = rgt[i][tp] - 1;
            int x = get(1, 0, n - 1, l, r);
            ans = max(ans, (r - l + 1) * 1ll * a[i] * x);
        }
        for (int i = 0; i < n; ++i) {
            swap(a[i], b[i]);
        }
    }

    for (int i = 0; i < n; ++i) {
        int l = max(lft[i][0] + 1, lft[i][1] + 1);
        int r = min(rgt[i][0] - 1, rgt[i][1] - 1);

        ans = max(ans, (r - l + 1) * 1ll * a[i] * b[i]);
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 5 ms 332 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 5 ms 332 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 5 ms 332 KB Output is correct
10 Correct 5 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 5 ms 332 KB Output is correct

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 5 ms 332 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 5 ms 332 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 5 ms 332 KB Output is correct
10 Correct 5 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 5 ms 332 KB Output is correct
13 Correct 2148 ms 7044 KB Output is correct
14 Correct 2088 ms 7316 KB Output is correct
15 Correct 2040 ms 7052 KB Output is correct
16 Incorrect 2040 ms 7016 KB Output isn't correct
17 Halted 0 ms 0 KB -