oj.uz

Submission #576085

# Submission time Handle Problem Language Result Execution time Memory
576085 2022-06-12T09:26:28 Z eecs 3D Histogram (COCI20_histogram) C++17
20 / 110
 2500 ms 2816 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200010;
int n, a[maxn], b[maxn];

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; }
        int mid = (l + r) / 2;
        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]);
        }
        for (int i = mid, j = mid, k = mid; i >= l; i--) {
            while (j < r && a[i] <= a[j + 1] && b[i] <= b[j + 1]) j++;
            if (j > mid) ans = max(ans, 1LL * a[i] * b[i] * (j - i + 1));
            while (k < r && a[i] <= a[k + 1]) k++;
            for (int p = k; p > mid && b[i] >= b[p]; p--) {
                ans = max(ans, 1LL * a[i] * b[p] * (p - i + 1));
            }
        }
        for (int i = mid + 1, j = mid + 1, k = mid + 1; i <= r; i++) {
            while (j > l && a[i] <= a[j - 1] && b[i] <= b[j - 1]) j--;
            if (j <= mid) ans = max(ans, 1LL * a[i] * b[i] * (i - j + 1));
            while (k > l && a[i] <= a[k - 1]) k--;
            for (int p = k; p <= mid && b[i] >= b[p]; p++) {
                ans = max(ans, 1LL * a[i] * b[p] * (i - p + 1));
            }
        }
        copy(_a.begin(), _a.end(), a + l);
        copy(_b.begin(), _b.end(), b + l);
    };
    solve(solve, 1, n);
    cout << ans << "\n";
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Correct 7 ms 340 KB Output is correct
6 Correct 4 ms 364 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 8 ms 340 KB Output is correct
10 Correct 7 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Execution timed out 2557 ms 2816 KB Time limit exceeded
14 Halted 0 ms 0 KB -