Submission #479418

#	Time	Username	Problem	Language	Result	Execution time	Memory
479418		ocarima	3D Histogram (COCI20_histogram)	C++14	0 / 110	1 ms	332 KiB

histogram

#include<bits/stdc++.h>

using namespace std;

// Problema E, div2 747

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define lli long long int
#define vi vector<int>
#define vlli vector<long long int>
#define pii pair<int, int>
#define plli pair<lli, lli>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define repa(i, a, b) for(int i = (a); i >= (b); i--)
#define repv(x, v) for(auto x : v)
#define debug(x) cout << #x << " = " << x << endl
#define debugsl(x) cout << #x << " = " << x << ", "
#define debugarr(x, a, b) cout << #x << " = ["; rep(i, a, b) cout << x[i] << ", "; cout << "]\n"
#define pb push_back
#define nl "\n"

#define MAXN 200003

lli n, a[MAXN], b[MAXN], ab[MAXN], res;

lli divide_y_venceras(lli l, lli r){
    if (l > r) return 0;
    if (l == r) return a[l] * b[l];

    lli ans = 0;
    lli mitad = (l + r) / 2;

    // OBTEN LO MEJOR DE AMBAS MITADES
    ans = max(divide_y_venceras(l, mitad - 1), divide_y_venceras(mitad + 1, r));

    // OBTEN LO MEJOR QUE PASE POR EL CENTRO

    // CONSTRUYE LA GRAFICA DE (a * b) HACIA AMBOS LADOS
    lli mina, minb;
    mina = a[mitad];
    minb = b[mitad];
    ab[mitad] = mina * minb;
    repa(i, mitad - 1, l){
        mina = min(mina, a[i]);
        minb = min(minb, b[i]);
        ab[i] = mina * minb;
    }
    mina = a[mitad];
    minb = b[mitad];
    rep(i, mitad + 1, r){
        mina = min(mina, a[i]);
        minb = min(minb, b[i]);
        ab[i] = mina * minb;
    }
    ab[l - 1] = ab[r + 1] = 0;

    // AUMENTA LA VENTANA HACIA AMBOS LADOS
    lli itl, itr, val;
    val = ab[mitad];
    itl = itr = mitad;
    while(l <= itl || itr <= r){
        while (l <= itl && ab[itl] >= val) --itl;
        while (itr <= r && ab[itr] >= val) ++itr;
        ans = max(ans, val * (itr - itl - 1));
        val = min(ab[max(itl, l)], ab[min(itr, r)]);
    }
    return ans;
}

int main()
{
    fastio;
    cin >> n;
    rep(i, 1, n) cin >> a[i] >> b[i];
    res = divide_y_venceras(1, n);
    cout << res;
}

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