Submission #377968

#	Time	Username	Problem	Language	Result	Execution time	Memory
377968		Vimmer	3D Histogram (COCI20_histogram)	C++14	0 / 110	11 ms	19148 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 200051
#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;

int 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 a = (x.F - y.F);

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

    if (a == 0)
    {
        if (a >= 0)
            return 1e18;

        return -1e18;
    }

    bool f1 = (a <= 0);

    bool f2 = (b <= 0);

    if (f1 && f2)
        return b / a + bool(b % a);

    return b / a;
}

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

    int 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 (int 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(t[v].back(), pt);

            if (b > a)
                break;

            t[v].pop_back();
        }

        t[v].PB(pt);
    }

    if (tl == tr) return;

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

    bld(v + v, tl, md);

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

ll get(int v, int tl, int tr, int l, int 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]) - 1]) > x)
            t[v].pop_back();

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

    int 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(int l, int r)
{
    for (int i = l; i <= r; i++)
        swap(a[i], b[i]);

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

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

    for (int 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 (int 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);

    int i1 = r;

    int i2 = md + 1;

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

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

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

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

            return;
        }

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

    solve(l, md);

    solve(md + 1, r);

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

    for (int 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 (int 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]);
    }

    int j = r;

    for (int i = md; i >= l; i--)
    {
        while (j >= md + 1 && (sf[i][0] > pr[j][0] || sf[i][1] > pr[j][1]))
            j--;

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

    j = l;

    for (int i = md + 1; i <= r; i++)
    {
        while (j <= md && (pr[i][0] > sf[j][0] || pr[i][1] > sf[j][1]))
            j++;

        if (j <= md)
            ans = max(ans, 1ll * (i - j + 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 (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];

    solve(1, n);

    pri(ans);
}

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