oj.uz

Submission #388668

# Submission time Handle Problem Language Result Execution time Memory
388668 2021-04-12T14:18:27 Z phathnv 3D Histogram (COCI20_histogram) C++11
110 / 110
 2060 ms 69216 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "Histogram"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> point;

const int N = 2e5 + 1;

point operator - (const point &a, const point &b){
    return point(a.X - b.X, a.Y - b.Y);
}

ll operator * (const point &a, const point &b){
    return a.X * b.Y - a.Y * b.X;
}

bool CW(point &a, point &b, point &c){
    return (b - a) * (c - b) < 0;
}

struct convexHull{
    vector <point> d;
    int ptr = -1;
    void reset(){
        d.clear();
    }
    void add(point p){
        d.push_back(p);
    }
    void findConvexHull(){
        vector <point> res;
        for(point p : d){
            while (res.size() > 1){
                if (!CW(res[res.size() - 2], res[res.size() - 1], p))
                    res.pop_back();
                else
                    break;
            }
            res.push_back(p);
        }
        swap(res, d);
        ptr = d.size() - 1;
    }
    ll findMax(point a){
        if (d.empty())
            return 0;
        while (ptr > 0 && a * d[ptr] < a * d[ptr - 1])
            ptr--;
        return a * d[ptr];
    }
} cvh;

struct segmentTree{
    convexHull d[N * 4];
    void reset(int id, int l, int r){
        d[id].reset();
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        reset(id << 1, l, mid);
        reset(id << 1 | 1, mid + 1, r);
    }
    void add(int id, int l, int r, int pos, point p){
        if (pos < l || r < pos)
            return;
        d[id].add(p);
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        add(id << 1, l, mid, pos, p);
        add(id << 1 | 1, mid + 1, r, pos, p);
    }
    void findConvexHull(int id, int l, int r){
        d[id].findConvexHull();
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        findConvexHull(id << 1, l, mid);
        findConvexHull(id << 1 | 1, mid + 1, r);
    }
    ll getMax(int id, int l, int r, int u, int v, point p){
        if (v < l || r < u || u > v)
            return 0;
        if (u <= l && r <= v)
            return d[id].findMax(p);
        int mid = (l + r) >> 1;
        return max(getMax(id << 1, l, mid, u, v, p), getMax(id << 1 | 1, mid + 1, r, u, v, p));
    }
} ST;

int n, a[N], b[N];

int minA[N], minB[N], x[N], y[N];

void readInput(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
}

ll calc(int l, int r, int d){
    if (l > r)
        return 0;

    int mid = (l + r + d) >> 1;
    minA[mid] = a[mid];
    minB[mid] = b[mid];
    for(int i = mid + 1; i <= r; i++){
        minA[i] = min(minA[i - 1], a[i]);
        minB[i] = min(minB[i - 1], b[i]);
    }
    for(int i = mid - 1; i >= l; i--){
        minA[i] = min(minA[i + 1], a[i]);
        minB[i] = min(minB[i + 1], b[i]);
    }

    ll res = 0;
    int ptr;
    /// minA and minB in left
    ptr = mid;
    for(int cur = mid; cur >= l; cur--){
        while (ptr <= r && minA[cur] <= minA[ptr] && minB[cur] <= minB[ptr])
            ptr++;
        res = max(res, (ll) (ptr - cur) * minA[cur] * minB[cur]);
    }
    /// minA in left and minB in right
    ptr = mid;
    for(int cur = mid; cur >= l; cur--){
        while (ptr <= r && minA[cur] <= minA[ptr])
            ptr++;
        y[cur] = ptr - 1;
    }
    ptr = mid;
    for(int cur = mid; cur >= l; cur--){
        while (ptr <= r && minB[cur] < minB[ptr])
            ptr++;
        x[cur] = ptr;
    }

    ST.reset(1, mid, r);
    for(int j = r; j >= mid; j--)
        ST.add(1, mid, r, j, point(minB[j], (ll) minB[j] * j));
    ST.findConvexHull(1, mid, r);
    for(int i = l; i <= mid; i++)
        res = max(res, ST.getMax(1, mid, r, x[i], y[i], point(minA[i], (ll) minA[i] * (i - 1))));

    res = max(res, calc(l, mid - 1, d));
    res = max(res, calc(mid + 1, r, d));

    return res;
}

void solve(){
    ll res = 0;
    res = max(res, calc(1, n, 0));
    reverse(a + 1, a + 1 + n);
    reverse(b + 1, b + 1 + n);
    res = max(res, calc(1, n, 1));
    cout << res;
}

int main(){
    readInput();
    solve();
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 25548 KB Output is correct
2 Correct 20 ms 25576 KB Output is correct
3 Correct 23 ms 25644 KB Output is correct
4 Correct 20 ms 25652 KB Output is correct
5 Correct 19 ms 25612 KB Output is correct
6 Correct 21 ms 25552 KB Output is correct
7 Correct 28 ms 25548 KB Output is correct
8 Correct 20 ms 25548 KB Output is correct
9 Correct 22 ms 25556 KB Output is correct
10 Correct 21 ms 25640 KB Output is correct
11 Correct 18 ms 25284 KB Output is correct
12 Correct 31 ms 25652 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 25548 KB Output is correct
2 Correct 20 ms 25576 KB Output is correct
3 Correct 23 ms 25644 KB Output is correct
4 Correct 20 ms 25652 KB Output is correct
5 Correct 19 ms 25612 KB Output is correct
6 Correct 21 ms 25552 KB Output is correct
7 Correct 28 ms 25548 KB Output is correct
8 Correct 20 ms 25548 KB Output is correct
9 Correct 22 ms 25556 KB Output is correct
10 Correct 21 ms 25640 KB Output is correct
11 Correct 18 ms 25284 KB Output is correct
12 Correct 31 ms 25652 KB Output is correct
13 Correct 1927 ms 69216 KB Output is correct
14 Correct 1999 ms 68964 KB Output is correct
15 Correct 1999 ms 68900 KB Output is correct
16 Correct 1937 ms 69124 KB Output is correct
17 Correct 1936 ms 69104 KB Output is correct
18 Correct 1884 ms 68832 KB Output is correct
19 Correct 1919 ms 69060 KB Output is correct
20 Correct 1948 ms 69088 KB Output is correct
21 Correct 1944 ms 69008 KB Output is correct
22 Correct 2060 ms 68936 KB Output is correct
23 Correct 126 ms 29612 KB Output is correct
24 Correct 2017 ms 69036 KB Output is correct