oj.uz

Submission #377993

# Submission time Handle Problem Language Result Execution time Memory
377993 2021-03-15T17:10:47 Z Vimmer 3D Histogram (COCI20_histogram) C++14
0 / 110
 15 ms 19232 KB 
#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 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(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(lst, 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]) - 2]) > 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 = md;

    int i2 = md + 1;

    for (int i = md; i >= l; i--)
    {
        while (i1 < r && pr[i1][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(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 j1 = md, j2 = md;

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

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

        int 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 (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];

    solve(1, n);

    pri(ans);
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19148 KB Output is correct
2 Correct 11 ms 19192 KB Output is correct
3 Correct 13 ms 19232 KB Output is correct
4 Correct 13 ms 19148 KB Output is correct
5 Correct 13 ms 19216 KB Output is correct
6 Correct 13 ms 19156 KB Output is correct
7 Correct 13 ms 19140 KB Output is correct
8 Correct 12 ms 19204 KB Output is correct
9 Correct 15 ms 19156 KB Output is correct
10 Correct 15 ms 19160 KB Output is correct
11 Incorrect 11 ms 19020 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19148 KB Output is correct
2 Correct 11 ms 19192 KB Output is correct
3 Correct 13 ms 19232 KB Output is correct
4 Correct 13 ms 19148 KB Output is correct
5 Correct 13 ms 19216 KB Output is correct
6 Correct 13 ms 19156 KB Output is correct
7 Correct 13 ms 19140 KB Output is correct
8 Correct 12 ms 19204 KB Output is correct
9 Correct 15 ms 19156 KB Output is correct
10 Correct 15 ms 19160 KB Output is correct
11 Incorrect 11 ms 19020 KB Output isn't correct
12 Halted 0 ms 0 KB -