Submission #375883

#	Time	Username	Problem	Language	Result	Execution time	Memory
375883		ne4eHbKa	3D Histogram (COCI20_histogram)	C++17	0 / 110	2 ms	360 KiB

histogram

#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
    void add(int &a, const int b) {if((a += b) >= md) a -= md;}
    void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
    int prod(const int a, const int b) {return ll(a) * b % md;}
};

int n;
const int N = 2e5 + 5;
int a[N], b[N];
pii l[N], r[N];
ll ans;

inline void upd(ll a, ll b, ll c) {umax(ans, a * b * c);}

struct line {
    int a;
    ll b;
    int i, x;
    int X(const line &f) const {
        ll t = f.b - b;
        ll u = a - f.a;
        ll z = (t < 0 ? t - u + 1 : t) / u;
        return z > n ? n : z < 1 ? 1 : z;
    }
};

deque<line> f;
int opt;

void add(pii &t, int i) {
    int a = t.sd;
    ll b = (ll)t.sd * (i + 1);
    line p{a, b, i, n};
    for(;;) {
        if(f.empty()) {
            f.push_back(p);
            return;
        }
        line &li = f.back();
        if(li.a == a) {
            li.i = i;
            return;
        }
        int x = li.X(p);
        if(x < li.x) {
            p.x = x;
            f.push_back(p);
            return;
        }
        f.pop_back();
        if(opt == len(f)) --opt;
    }
}

void del(int i) {
    for(; !f.empty() && f.front().i <= i; f.pop_front())
        if(opt > 0) --opt;
}

void calc(pii *l, int n, pii *r, int m) {
    f.clear();
    int fi{}, se{};
    opt = 0;
    for(int i = 0; i < n; ++i) {
        while(fi < m && r[fi].ft >= l[i].ft) add(r[fi], fi), ++fi;
        while(se < fi && r[se].sd >= l[i].sd) del(se++);
        upd(l[i].ft, l[i].sd, se + i + 1);
        while(opt + 1 < len(f) && f[opt + 1].x >= i + 1) ++opt;
        if(opt < len(f)) umax(ans, l[i].ft * (f[opt].b + f[opt].a * ll(i + 1)));
    }
}

void calc(int L, int R) {
    int MD = L + R >> 1;
    if(L < MD) calc(L, MD - 1);
    if(MD + 1 < R) calc(MD + 1, R);
    int A = +inf, B = +inf, n = 0, m = 0;
    for(int i = MD; i >= L; --i) {
        umin(A, a[i]);
        umin(B, b[i]);
        l[n++] = {A, B};
    }
    A = +inf, B = +inf;
    for(int i = MD + 1; i <= R; ++i) {
        umin(A, a[i]);
        umin(B, b[i]);
        r[m++] = {A, B};
    }
    calc(l, n, r, m);
    calc(r, m, l, n);
}

void solve() {
    cin >> n;
    ans = 0;
    for(int i = 0; i < n; ++i)
        cin >> a[i] >> b[i],
        upd(a[i], b[i], 1);
    calc(0, n - 1);
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
//    freopen("file.in", "r", stdin);
//    freopen("file.out", "w", stdout);
#else
    system("color a");
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while(t--)
#endif
    solve();
}

Compilation message (stderr)

histogram.cpp: In function 'void calc(int, int)':
histogram.cpp:96:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |     int MD = L + R >> 1;
      |              ~~^~~

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