Submission #1259823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259823		duckindog	3D Histogram (COCI20_histogram)	C++20	110 / 110	68 ms	8264 KiB

histogram

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10,
            MAX = 1'000'000'000;
int n;
int a[N], b[N];

struct Line { 
    long long a, b, idx;
    Line(long long a = 0, long long b = 0, int idx = 0) : a(a), b(b), idx(idx) {}
    long long cal(int x) { return a * x + b; }
};
int top, bot;
Line hull[N];

long long ccw(const Line &a, const Line &b, const Line &c){
    long long dx1 = b.a - a.a, dy1 = b.b - a.b;
    long long dx2 = c.a - b.a, dy2 = c.b - b.b;
    return dx1 * dy2 - dx2 * dy1;
}

inline void clear() { bot = 1; top = 0; }
inline void add(Line line) { 
    for (; top > bot && ccw(hull[top - 1], hull[top], line) <= 0; --top);
    hull[++top] = line;
}
inline void del(int idx) { 
    for (; bot <= top && hull[bot].idx < idx; ++bot);
}
inline long long query(int x) { 
    if (bot > top) return 0;

    int l = bot, r = top - 1, ret = bot;
    while (l <= r) { 
        int mid = (l + r) >> 1;
        if (hull[mid].cal(x) <= hull[mid + 1].cal(x)) l = ret = mid + 1;
        else r = mid - 1;
    }
    return hull[ret].cal(x);
}

int minA[N], minB[N];
long long answer;
void dnc(int l, int r) { 
    int mid = (l + r) >> 1;

    for (int i = mid, it = mid + 1; i >= l; --i) { 
        minA[i] = (i == mid ? a[i] : min(minA[i + 1], a[i]));
        minB[i] = (i == mid ? b[i] : min(minB[i + 1], b[i]));

        for (; it <= r && a[it] >= minA[i] && b[it] >= minB[i]; ++it);
        answer = max(answer, 1ll * minA[i] * minB[i] * (it - i)); 
    }
    for (int i = mid + 1, it = mid; i <= r; ++i) { 
        minA[i] = (i == mid + 1 ? a[i] : min(minA[i - 1], a[i]));
        minB[i] = (i == mid + 1 ? b[i] : min(minB[i - 1], b[i]));

        for (; it >= l && a[it] >= minA[i] && b[it] >= minB[i]; --it);
        answer = max(answer, 1ll * minA[i] * minB[i] * (i - it));
    }
    
    clear();
    for (int i = mid, itL = mid + 1, itR = mid + 1; i >= l; --i) { 
        for (; itR <= r && a[itR] >= minA[i]; ++itR) { 
            add(Line(minB[itR], 1ll * minB[itR] * itR, itR));
        }
        for (; itL <= r && b[itL] > minB[i]; ++itL);
        del(itL);

        answer = max(answer, 1ll * minA[i] * query(-(i - 1)));
    }
    clear();
    for (int i = mid + 1, itR = mid, itL = mid; i <= r; ++i) { 
        for (; itL >= l && a[itL] >= a[i]; --itL) { 
            add(Line(minB[itL], 1ll * minB[itL] * -(itL - 1), -(itL - 1)));
        }
        for (; itR >= l && b[itR] > minB[i]; --itR);
        del(-(itR - 1));

        answer = max(answer, 1ll * minA[i] * query(i));
    }

    if (l == r) return;
    dnc(l, mid);
    dnc(mid + 1, r);
}

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

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

    dnc(1, n);
    cout << answer << "\n";
}

• Subtask 1: 20 / 20
• Subtask 2: 90 / 90