Submission #388668

#	Time	Username	Problem	Language	Result	Execution time	Memory
388668		phathnv	3D Histogram (COCI20_histogram)	C++11	110 / 110	2060 ms	69216 KiB

histogram

#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 / 20
• Subtask 2: 90 / 90