oj.uz

Submission #375891

# Submission time Handle Problem Language Result Execution time Memory
375891 2021-03-10T08:01:49 Z ne4eHbKa 3D Histogram (COCI20_histogram) C++17
110 / 110
 123 ms 3456 KB 
#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;
        if(u < 0) u *= -1, t *= -1;
        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, x;
    ll b = (ll)t.sd * (i + 1);
    line p{a, b, i, n};
    for(;;) {
        if(f.empty()) {
            if(opt + 1 == len(f)) ++opt;
            f.push_back(p);
            return;
        }
        line &li = f.back();
        if(li.a == a)
            goto lb0;
        x = li.X(p);
        if(x < li.x) {
            p.x = x;
            if(opt + 1 == len(f)) ++opt;
            f.push_back(p);
            return;
        }
        lb0: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 && f[opt].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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 105 ms 3352 KB Output is correct
14 Correct 81 ms 3456 KB Output is correct
15 Correct 93 ms 3432 KB Output is correct
16 Correct 104 ms 3424 KB Output is correct
17 Correct 93 ms 3340 KB Output is correct
18 Correct 114 ms 3420 KB Output is correct
19 Correct 100 ms 3428 KB Output is correct
20 Correct 101 ms 3408 KB Output is correct
21 Correct 121 ms 3436 KB Output is correct
22 Correct 94 ms 3396 KB Output is correct
23 Correct 9 ms 588 KB Output is correct
24 Correct 123 ms 3396 KB Output is correct