Submission #503058

# Submission time Handle Problem Language Result Execution time Memory
503058 2022-01-07T04:42:20 Z maomao90 3D Histogram (COCI20_histogram) C++17
110 / 110
700 ms 122100 KB
// 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

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]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 3 ms 676 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 3 ms 664 KB Output is correct
5 Correct 2 ms 688 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 636 KB Output is correct
9 Correct 4 ms 1012 KB Output is correct
10 Correct 3 ms 1052 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 3 ms 928 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 676 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 3 ms 664 KB Output is correct
5 Correct 2 ms 688 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 636 KB Output is correct
9 Correct 4 ms 1012 KB Output is correct
10 Correct 3 ms 1052 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 3 ms 928 KB Output is correct
13 Correct 617 ms 110868 KB Output is correct
14 Correct 228 ms 43468 KB Output is correct
15 Correct 558 ms 96968 KB Output is correct
16 Correct 664 ms 120580 KB Output is correct
17 Correct 541 ms 60948 KB Output is correct
18 Correct 502 ms 76020 KB Output is correct
19 Correct 453 ms 69956 KB Output is correct
20 Correct 552 ms 83472 KB Output is correct
21 Correct 700 ms 120424 KB Output is correct
22 Correct 584 ms 122100 KB Output is correct
23 Correct 40 ms 5720 KB Output is correct
24 Correct 355 ms 12872 KB Output is correct