Submission #378003

#	Time	Username	Problem	Language	Result	Execution time	Memory
378003		Vimmer	3D Histogram (COCI20_histogram)	C++14	110 / 110	749 ms	41984 KiB

histogram

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")

#define N 250051
#define NN 1005000
#define PB push_back
#define M ll(1e9 + 7)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pri(x) cout << x << endl
#define endl '\n'
#define _ << " " <<
#define F first
#define S second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
//typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

typedef long double ld;
typedef unsigned long long ull;
typedef short int si;

ll n, a[N], b[N], pr[N][2], sf[N][2];

vector <pair <ll, ll> > t[N * 4];

ll ans = 0;

ll inter(pair <ll, ll> x, pair <ll, ll> y)
{
    ll k = (y.F - x.F);

    ll b = (x.S - y.S);

    if (k == 0)
    {
        if (b > 0)
            return -1e18;

        return 1e18;
    }

    bool f1 = (k <= 0);

    bool f2 = (b <= 0);

    if (f1 == f2)
        return b / k + bool(b % k);

    return b / k;
}

void bld(ll v, ll tl, ll tr)
{
    t[v].clear();

    ll ps = tl;

    while (ps < tr && pr[ps + 1][0] == pr[tl][0])
        ps++;

    t[v].PB({-pr[ps][0], 1ll * pr[ps][0] * ps});

    for (ll i = ps + 1; i <= tr; i++)
    {
        pair <ll, ll> pt = {-pr[i][0], 1ll * pr[i][0] * i};

        while(sz(t[v]) > 1)
        {
            pair <ll, ll> lst = t[v][sz(t[v]) - 2];

            ll a = inter(lst, t[v].back());

            ll b = inter(lst, pt);

            if (b > a)
                break;

            t[v].pop_back();
        }

        t[v].PB(pt);
    }

    if (tl == tr) return;

    ll md = (tl + tr) >> 1;

    bld(v + v, tl, md);

    bld(v + v + 1, md + 1, tr);
}

ll get(ll v, ll tl, ll tr, ll l, ll r, ll x)
{
    if (tr < l || l > r || r < tl || tl > tr) return 0;

    if (l <= tl && tr <= r)
    {
        while (sz(t[v]) > 1 && inter(t[v].back(), t[v][sz(t[v]) - 2]) > x)
            t[v].pop_back();

        return t[v].back().S + t[v].back().F * x;
    }

    ll md = (tl + tr) >> 1;

    return max(get(v + v, tl, md, l, r, x), get(v + v + 1, md + 1, tr, l, r, x));
}

void calc(ll l, ll r)
{
    for (ll i = l; i <= r; i++)
        swap(a[i], b[i]);

    ll md = (l + r) >> 1;

    sf[md][0] = a[md];
    sf[md][1] = b[md];

    for (ll i = md - 1; i >= l; i--)
    {
        sf[i][0] = min(sf[i + 1][0], a[i]);
        sf[i][1] = min(sf[i + 1][1], b[i]);
    }

    pr[md + 1][0] = a[md + 1];
    pr[md + 1][1] = b[md + 1];

    for (ll i = md + 2; i <= r; i++)
    {
        pr[i][0] = min(pr[i - 1][0], a[i]);
        pr[i][1] = min(pr[i - 1][1], b[i]);
    }

    bld(1, md + 1, r);

    ll i1 = md;

    ll i2 = md + 1;

    for (ll i = md; i >= l; i--)
    {
        while (i1 < r && pr[i1 + 1][1] >= sf[i][1])
            i1++;

        while (i2 <= r && sf[i][0] < pr[i2][0])
            i2++;

        if (i2 <= i1)
            ans = max(ans, get(1, md + 1, r, i2, i1, i - 1) * sf[i][1]);
    }
}

void solve(ll l, ll r)
{
    if (l == r)
        {
            ans = max(ans, 1ll * a[l] * b[l]);

            return;
        }

    ll md = (l + r) >> 1;

    solve(l, md);

    solve(md + 1, r);

    sf[md][0] = a[md];
    sf[md][1] = b[md];

    for (ll i = md - 1; i >= l; i--)
    {
        sf[i][0] = min(sf[i + 1][0], a[i]);
        sf[i][1] = min(sf[i + 1][1], b[i]);
    }

    pr[md + 1][0] = a[md + 1];
    pr[md + 1][1] = b[md + 1];

    for (ll i = md + 2; i <= r; i++)
    {
        pr[i][0] = min(pr[i - 1][0], a[i]);
        pr[i][1] = min(pr[i - 1][1], b[i]);
    }

    ll j1 = md, j2 = md;

    for (ll i = md; i >= l; i--)
    {
        while (j1 < r && pr[j1 + 1][0] >= sf[i][0])
            j1++;

        while (j2 < r && pr[j2 + 1][1] >= sf[i][1])
            j2++;

        ll mx = min(j1, j2);

        if (mx > md)
            ans = max(ans, 1ll * (mx - i + 1) * sf[i][0] * sf[i][1]);
    }

    j1 = md + 1; j2 = md + 1;

    for (ll i = md + 1; i <= r; i++)
    {
        while (j1 > l && sf[j1 - 1][0] >= pr[i][0])
            j1--;

        while (j2 > l && sf[j2 - 1][1] >= pr[i][1])
            j2--;

        ll mx = max(j1, j2);

        if (mx < md + 1)
            ans = max(ans, 1ll * (i - mx + 1) * pr[i][0] * pr[i][1]);
    }

    calc(l, r);

    calc(l, r);
}

int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("1.in", "r", stdin);

    cin >> n;

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

    solve(1, n);

    pri(ans);
}

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