oj.uz

답안 #494452

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
494452 2021-12-15T13:22:46 Z istlemin 3D Histogram (COCI20_histogram) C++14
0 / 110
 4 ms 580 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 580 KB Output isn't correct
2 Halted 0 ms 0 KB -