Submission #503058

#	Time	Username	Problem	Language	Result	Execution time	Memory
503058		maomao90	3D Histogram (COCI20_histogram)	C++17	110 / 110	700 ms	122100 KiB

histogram

// Cast your cares on the Lord and he will sustain you;
// he will never let the righteous be shaken
// Psalms 55:22
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) printf(args)
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 200005

int n;
int a[MAXN], b[MAXN];

struct line {
    ll m, c;
    ll isect(const line &o) const {
        return (c - o.c) / (o.m - m);
    }
    ll eval(ll x) {
        return m * x + c;
    }
};
struct event {
    line l;
    int s, e;
};

ll ans;
int pfa[MAXN], pfb[MAXN];
int st[MAXN];
deque<line> dq;
void insert(line l) {
    if (!dq.empty() && dq.back().m == l.m) {
        if (dq.back().c >= l.c) {
            return;
        } 
        dq.pop_back();
    }
    assert(dq.empty() || dq.back().m < l.m);
    while (dq.size() >= 2 && l.isect(dq[dq.size() - 1]) <= 
            l.isect(dq[dq.size() - 2])) {
        dq.pop_back();
    }
    dq.pb(l);
}
void dnct(int s, int e, vector<event> ev) {
    if (ev.empty()) return;
    int m = s + e >> 1;
    vector<event> lev, rev;
    dq.clear();
    for (auto ce : ev) {
        if (ce.s <= s && ce.e >= e) {
            insert(ce.l);
        } else {
            if (ce.s <= m) {
                lev.pb(ce);
            }
            if (ce.e > m) {
                rev.pb(ce);
            }
        }
    }
    if (!dq.empty()) {
        REP (i, s, e + 1) {
            while (dq.size() >= 2 && dq[0].eval(i) <= dq[1].eval(i)) {
                dq.pop_front();
            }
            mxto(ans, (ll) pfa[i] * dq[0].eval(i));
        }
    }
    dnct(s, m, lev); dnct(m + 1, e, rev);
}
int zz;
void dnc(int s, int e) {
    if (s == e) {
        mxto(ans, (ll) a[s] * b[s]);
        return;
    }
    assert(s < e);
    int m = s + e + zz>> 1;
    REP (i, m + 1, e + 1) {
        pfa[i] = a[i];
        if (i != m + 1) {
            mnto(pfa[i], pfa[i - 1]);
        }
        pfb[i] = b[i];
        if (i != m + 1) {
            mnto(pfb[i], pfb[i - 1]);
        }
    }
    RREP (i, m, s) {
        pfa[i] = a[i];
        if (i != m) {
            mnto(pfa[i], pfa[i + 1]);
        }
        pfb[i] = b[i];
        if (i != m) {
            mnto(pfb[i], pfb[i + 1]);
        }
    }
    // a and b minimum on left
    int ptr = m;
    RREP (i, m, s) {
        while (ptr + 1 <= e &&
                pfa[i] <= pfa[ptr + 1] && pfb[i] <= pfb[ptr + 1]) {
            ptr++;
        }
        mxto(ans, (ll) pfa[i] * pfb[i] * (ptr - i + 1));
    }
    // a minimum on left, b minimum on right
    vector<event> ev;
    int l = m + 1, r = m;
    RREP (i, m, s) {
        while (r + 1 <= e && pfa[i] <= pfa[r + 1]) {
            r++;
            st[r] = i;
        }
        while (l <= r && pfb[i] < pfb[l]) {
            if (st[l] != i) {
                line tmp = {-pfb[l], (ll) (l + 1) * pfb[l]};
                ev.pb({tmp, i + 1, st[l]});
            }
            l++;
        }
    }
    while (l <= r) {
        line tmp = {-pfb[l], (ll) (l + 1) * pfb[l]};
        ev.pb({tmp, s, st[l]});
        l++;
    }
    dnct(s, m, ev);
    dnc(s, m - zz); dnc(m + 1 - zz, e);
}

int main() {
    scanf("%d", &n);
    REP (i, 0, n) {
        scanf("%d%d", &a[i], &b[i]);
    }
    dnc(0, n - 1);
    reverse(a, a + n);
    reverse(b, b + n);
    zz = 1;
    dnc(0, n - 1);
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

histogram.cpp: In function 'void dnct(int, int, std::vector<event>)':
histogram.cpp:77:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |     int m = s + e >> 1;
      |             ~~^~~
histogram.cpp: In function 'void dnc(int, int)':
histogram.cpp:109:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |     int m = s + e + zz>> 1;
      |             ~~~~~~^~~~
histogram.cpp: In function 'int main()':
histogram.cpp:165:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
histogram.cpp:167:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         scanf("%d%d", &a[i], &b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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