Submission #490403

#	Time	Username	Problem	Language	Result	Execution time	Memory
490403		Victor	3D Histogram (COCI20_histogram)	C++17	0 / 110	1 ms	588 KiB

histogram

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

int n, height[18][200001], len[18][200001];
int sh[200001], sl[200001], eh[200001], el[200001];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    cin >> n;
    rep(i, 0, n) cin >> height[0][i] >> len[0][i];
    rep(j, 1, 18) rep(i, 0, n - (1 << j) + 1) {
        height[j][i] = min(height[j - 1][i], height[j - 1][i + (1 << (j - 1))]);
        len[j][i] = min(len[j - 1][i], len[j - 1][i + (1 << (j - 1))]);
    }

    deque<ii> h, l;
    h.emplace_front(0, -1);
    l.emplace_front(0, -1);
    rep(i, 0, n) {
        int cur_h = height[0][i], cur_l = len[0][i];

        while (h.front().first >= cur_h) h.pop_front();
        while (l.front().first >= cur_l) l.pop_front();

        sh[i] = h.front().second + 1;
        sl[i] = l.front().second + 1;

        h.emplace_front(cur_h, i);
        h.emplace_front(cur_l, i);
    }
    h.clear();
    l.clear();

    h.emplace_front(0, n);
    l.emplace_front(0, n);
    per(i, 0, n) {
        int cur_h = height[0][i], cur_l = len[0][i];

        while (h.front().first >= cur_h) h.pop_front();
        while (l.front().first >= cur_l) l.pop_front();

        eh[i] = h.front().second - 1;
        el[i] = l.front().second - 1;

        h.emplace_front(cur_h, i);
        h.emplace_front(cur_l, i);
    }

    ll ans = 0;
    rep(i, 0, n) {
        //cout<<"i = "<<i<<endl;
        rep(j, 0, 4) {
            int start, end;
            if(j<2)start=sh[i];
            else start=sl[i];

            if(j%2)end=el[i];
            else end=eh[i];        

            int cur_h, cur_l;
            int dist = (end - start + 1);
            int power = log2(dist);

            //cout<<"start = "<<start<<" end = "<<end<<" cur_h = "<<cur_h<<" cur_l = "<<cur_l<<" dist = "<<dist<<" power = "<<power<<endl;

            cur_h = min(height[power][start], height[power][end - (1 << power) + 1]);
            cur_l = min(len[power][start], len[power][end - (1 << power) + 1]);
            ans = max(ans, ll(dist) * cur_h * cur_l);
        }
        //cout<<endl;
    }

    cout<<ans<<endl;
    return 0;
}

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