Submission #494452

#	Time	Username	Problem	Language	Result	Execution time	Memory
494452		istlemin	3D Histogram (COCI20_histogram)	C++14	0 / 110	4 ms	580 KiB

histogram

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(ll i = a; i < (b); ++i)
#define rrep(i, a, b) for(ll i = b-1; i >= (a); --i)
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;

ll n;
vi a;
vi b;

ll ans = 0;

void dnc(ll l, ll r){
    if(l==r) return;
    ll m = (l+r)/2;

    unordered_map<ll,ll> ra;
    unordered_map<ll,ll> rb;
    ra[m] = a[m];
    rb[m] = b[m];
    rep(i,m+1,r){
        ra[i] = min(ra[i-1],a[i]);
        rb[i] = min(rb[i-1],b[i]);
    }
    
    unordered_map<ll,ll> la;
    unordered_map<ll,ll> lb;
    la[m] = a[m];
    lb[m] = b[m];
    rrep(i,l,m){
        la[i] = min(la[i+1],a[i]);
        lb[i] = min(lb[i+1],b[i]);
    }

    ll ri = m;
    rrep(i,l,m+1){
        while(ri<r-1 && ra[ri+1]>=la[i] && rb[ri+1]>=lb[i]) ri++;
        ans = max(ans, (ri-i+1)*la[i]*lb[i]);
    }
    dnc(l,m);
    dnc(m+1,r);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
    cin>>n;
    a.resize(n);
    b.resize(n);
    rep(i,0,n) cin>>a[i]>>b[i];

    dnc(0,n);
    cout<<ans<<endl;
}

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