Submission #333889

#	Time	Username	Problem	Language	Result	Execution time	Memory
333889		wiwiho	3D Histogram (COCI20_histogram)	C++14	20 / 110	343 ms	78788 KiB

histogram

#include <bits/stdc++.h>

#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()

using namespace std;

typedef long long ll;

const ll MAX = 2147483647;

int argmin(vector<ll>& a, int x, int y){
    return a[x] < a[y] ? x : y;
}

struct SparseTable{

    vector<vector<int>> st;

    void build(vector<ll>& a){
        int n = a.size();
        st.resize(n, vector<int>(20));
        for(int i = 0; i < n; i++) st[i][0] = i;
        for(int i = 1; i < 20; i++){
            for(int j = 0; j + (1 << i) - 1 < n; j++){
                st[j][i] = argmin(a, st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
            }
        }
    }

    int query(vector<ll>& a, int l, int r){
        int lg = __lg(r - l + 1);
        return argmin(a, st[l][lg], st[r - (1 << lg) + 1][lg]);
    }

};

int n;
vector<ll> a, b;
SparseTable sta, stb;

map<pii, int> tmp;
ll f2(int l, int r){
    if(l > r) return 0;
    if(tmp.find(mp(l, r)) != tmp.end()) return tmp[mp(l, r)];
    int m = stb.query(b, l, r);
    //cerr << l << " " << r << " " << m << "\n";
    tmp[mp(l, r)] = max({b[m] * (r - l + 1), f2(l, m - 1), f2(m + 1, r)});
    return tmp[mp(l, r)];
}

ll f1(int l, int r){
    if(l > r) return 0;
    int m = sta.query(a, l, r);
    return max({a[m] * f2(l, r), f1(l, m - 1), f1(m + 1, r)});
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    a.resize(n);
    b.resize(n);
    for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
    sta.build(a);
    stb.build(b);
    
    cout << f1(0, n - 1) << "\n";
    
    return 0;
}

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