Submission #498557

#	Time	Username	Problem	Language	Result	Execution time	Memory
498557		Victor	3D Histogram (COCI20_histogram)	C++17	0 / 110	13 ms	7900 KiB

histogram

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

int n;
ll h[200001], w[200001];
bool print = 0;

struct Node {
    int lo, hi;
    vpll points, hull;
    Node *l, *r;

    Node(const vector<pair<ll, pll>> &vec, int L, int R) : lo(L), hi(R) {
        if (hi - lo == 1) {
            points.emplace_back(vec[lo].second);
            hull.pb(points[0]);

        } else {
            int mid = (hi + lo) / 2;
            l = new Node(vec, lo, mid);
            r = new Node(vec, mid, hi);

            points = l->points;
            trav(point, r->points) points.emplace_back(point);

            hull.emplace_back(points[0]);
            hull.emplace_back(points[1]);
            rep(i, 2, sz(points)) {
                pll cur = points[i];
                pll prev = hull.back();
                pll pprev = hull[sz(hull) - 2];

                while (slope(pprev, prev) < slope(pprev, cur)) {
                    hull.pop_back();
                    if (sz(hull) == 1) break;
                    prev = hull.back();
                    pprev = hull[sz(hull) - 2];
                }

                hull.push_back(cur);
            }
        }
    }

    double slope(pll p1, pll p2) { return double(p2.second - p1.second) / double(p2.first - p1.first); }

    ll query(int L, int R, pll point) {
        if (R <= lo || hi <= L) return 0;
        if (L <= lo && hi <= R) {
            
            ll ans = 0;
            int cur_lo = 0, cur_hi = sz(hull) - 1;
            while (cur_hi - cur_lo >= 3) {
                int m1 = cur_lo + (cur_hi - cur_lo) / 3, m2 = cur_hi - (cur_hi - cur_lo) / 3;
                ll ans1 = volume(point, hull[m1]);
                ll ans2 = volume(point, hull[m2]);
                if (ans1 > ans2)
                    cur_hi = m2;
                else
                    cur_lo = m1;
            }

            rep(i, cur_lo, cur_hi + 1) ans = max(ans, volume(point, hull[i]));
            return ans;
        }

        return max(l->query(L, R, point), r->query(L, R, point));
    }

    ll volume(pll p1, pll p2) { return p1.first * p2.first + p1.second * p2.second; }
};

ll solve(int lo, int hi) {
    if (hi < lo) return 0;
    if (lo == hi) return h[lo] * w[hi];

    int mid = (lo + hi) / 2;
    ll ansL = solve(lo, mid - 1), ansR = solve(mid + 1, hi);
    ll ans = max(ansL, ansR);

    rep(_, 0, 2) {
        int j = mid + 1;
        ll curh = h[mid], curw = w[mid];
        per(i, lo, mid + 1) {
            curh = min(curh, h[i]);
            curw = min(curw, w[i]);
            while (j <= hi && curh <= h[j] && curw <= w[j]) ++j;
            ans = max(ans, curh * curw * (j - i));
        }

        curw = INF;
        vector<pair<ll, pll>> points;
        if (hi - lo == 5) print = 1;
        rep(i, mid, hi + 1) {
            curw = min(curw, w[i]);
            points.pb({-i, {curw, curw * i}});
        }
        sort(all(points));
        Node segtree(points, 0, sz(points));

        curh = h[mid], curw = w[mid];
        int start = mid, stop = mid;
        per(i, lo, mid + 1) {
            curh = min(curh, h[i]);
            curw = min(curw, w[i]);
            while (stop <= hi && curh <= h[stop]) ++stop;
            while (start <= hi && curw < w[start]) ++start;

            if (start < stop) {
                ans = max(ans, segtree.query((hi - stop + 1) - mid, (hi - start + 1) - mid, {curh * (1 - i), curh}));
            }
        }

        reverse(h + lo, h + hi + 1);
        reverse(w + lo, w + hi + 1);
    }

    //cout << "lo = " << lo << " hi = " << hi << endl;
    //cout << "ans = " << ans << endl
    //     << endl;

    return ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    cin >> n;
    rep(i, 0, n) cin >> h[i] >> w[i];
    ll ans = solve(0, n - 1);
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

histogram.cpp: In constructor 'Node::Node(const std::vector<std::pair<long long int, std::pair<long long int, long long int> > >&, int, int)':
histogram.cpp:8:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define rep(i, a, b) for (int i = (a); i < (b); ++i)
      |                                          ^
histogram.cpp:57:13: note: in expansion of macro 'rep'
   57 |             rep(i, 2, sz(points)) {
      |             ^~~

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