oj.uz

Submission #630171

# Submission time Handle Problem Language Result Execution time Memory
630171 2022-08-15T19:56:37 Z vovamr 3D Histogram (COCI20_histogram) C++17
20 / 110
 946 ms 128980 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 2e5 + 100;

struct line {
	ll k, b;
	line() : k(0), b(0) {}
	line(ll k, ll b) : k(k), b(b) {}
	inline ll operator()(const ll &x) { return k * x + b; }
};
inline bool operator < (const line &a, const line &b) {
	if (a.k < b.k) return 1;
	else if (a.k > b.k) return 0;
	else return a.b > b.b;
}
inline bool bad(const line &a, const line &b, const line &c) {
	return (ld)(a.b - c.b) * (b.k - a.k) <= (ld)(c.k - a.k) * (a.b - b.b);
}

int a[N], b[N];
int mna[N], mnb[N];

int ptr[N];
ve<line> cht[4 * N], t[4 * N];

inline void build(int v, int vl, int vr, const int &border) {
	if (vl == vr) {
		if (vl <= border)
			cht[v] = {line(mnb[vl], -vl * 1ll * mnb[vl])};
		else
			cht[v] = {line(mnb[vl], +vl * 1ll * mnb[vl])};
		return;
	}

	int m = vl + vr >> 1;
	build(2 * v + 1, vl, m, border);
	build(2 * v + 2, m + 1, vr, border);
	merge(all(cht[2 * v + 1]), all(cht[2 * v + 2]), back_inserter(cht[v]));

	ve<line> s;
	for (auto &c : cht[v]) {
		if (!sz(s)) s.pb(c);
		else {
			if (s.back().k == c.k) continue;
			while (sz(s) >= 2) {
				const line &a = s[sz(s) - 2];
				const line &b = s[sz(s) - 1];
				if (bad(a, b, c)) s.pop_back();
				else break;
			} s.pb(c);
		}
	} t[v] = s;
}
inline void clear(int v, int vl, int vr) {
	cht[v].clear(); t[v].clear();
	ptr[v] = 0;
	if (vl == vr) return;
	int m = vl + vr >> 1;
	clear(2 * v + 1, vl, m);
	clear(2 * v + 2, m + 1, vr);
}

inline ll get(int v, int vl, int vr, int l, int r, ll x) {
	if (l > r || !sz(t[v])) return -inf;
	else if (vl == l && vr == r) {
		while (ptr[v] + 1 < sz(t[v]) && t[v][ptr[v]](x) < t[v][ptr[v] + 1](x)) ++ptr[v];
		return t[v][ptr[v]](x);
	}
	int m = vl + vr >> 1;
	return max(get(2*v+1,vl,m,l,min(r,m),x),get(2*v+2,m+1,vr,max(l,m+1),r,x));
}

ll ans = 0;

inline void solve(int l, int r) {
	if (l == r) return void(chmax(ans, a[l] * 1ll * b[l]));

	int m = l + r >> 1;

	mna[m] = a[m], mna[m + 1] = a[m + 1];
	for (int i = m - 1; i >= l; --i) mna[i] = min(mna[i + 1], a[i]);
	for (int i = m + 2; i <= r; ++i) mna[i] = min(mna[i - 1], a[i]);

	mnb[m] = b[m], mnb[m + 1] = b[m + 1];
	for (int i = m - 1; i >= l; --i) mnb[i] = min(mnb[i + 1], b[i]);
	for (int i = m + 1; i <= r; ++i) mnb[i] = min(mnb[i - 1], b[i]);

	int p1, p2;

	p1 = p2 = m;
	for (int i = m + 1; i <= r; ++i) {
		while (p1 >= l && mna[p1] >= mna[i]) --p1;
		while (p2 >= l && mnb[p2] >= mnb[i]) --p2;
		int pos = max(p1, p2) + 1;
		if (pos <= m) {
			assert(min(mna[pos], mna[i]) == mna[i]);
			assert(min(mnb[pos], mnb[i]) == mnb[i]);
			chmax(ans, mna[i] * 1ll * mnb[i] * 1ll * (i - pos + 1));
		}
	}

	p1 = p2 = m + 1;
	for (int i = m; i >= l; --i) {
		while (p1 <= r && mna[p1] > mna[i]) ++p1;
		while (p2 <= r && mnb[p2] > mnb[i]) ++p2;
		int pos = min(p1, p2) - 1;
		if (pos >= m + 1) {
			assert(min(mna[pos], mna[i]) == mna[i]);
			assert(min(mnb[pos], mnb[i]) == mnb[i]);
			chmax(ans, mna[i] * 1ll * mnb[i] * 1ll * (pos - i + 1));
		}
	}

	build(0, l, r, m);

	p1 = p2 = m;
	for (int i = m + 1; i <= r; ++i) {
		while (p1 >= l && mna[p1] >= mna[i]) --p1;
		while (p2 >= l && mnb[p2] >= mnb[i]) --p2;
		if (p1 + 1 <= p2) {
			ll C = get(0, l, r, p1 + 1, p2, i + 1);
			if (C == -inf) continue;
			chmax(ans, mna[i] * 1ll * C);
		}
	}

	p1 = p2 = m + 1;
	for (int i = m; i >= l; --i) {
		while (p1 <= r && mna[p1] > mna[i]) ++p1;
		while (p2 <= r && mnb[p2] > mnb[i]) ++p2;
		if (p2 <= p1 - 1) {
			ll C = get(0, l, r, p2, p1 - 1, -(i - 1));
			if (C == -inf) continue;
			chmax(ans, mna[i] * 1ll * C);
		}
	}

	clear(0, l, r);

	solve(l, m);
	solve(m + 1, r);
}

inline void solve() {
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];

	solve(0, n - 1);
	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message

histogram.cpp: In function 'void build(int, int, int, const int&)':
histogram.cpp:55:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |  int m = vl + vr >> 1;
      |          ~~~^~~~
histogram.cpp: In function 'void clear(int, int, int)':
histogram.cpp:78:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |  int m = vl + vr >> 1;
      |          ~~~^~~~
histogram.cpp: In function 'long long int get(int, int, int, int, int, long long int)':
histogram.cpp:89:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |  int m = vl + vr >> 1;
      |          ~~~^~~~
histogram.cpp: In function 'void solve(int, int)':
histogram.cpp:98:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |  int m = l + r >> 1;
      |          ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 38484 KB Output is correct
2 Correct 22 ms 38536 KB Output is correct
3 Correct 25 ms 38484 KB Output is correct
4 Correct 21 ms 38444 KB Output is correct
5 Correct 21 ms 38512 KB Output is correct
6 Correct 21 ms 38456 KB Output is correct
7 Correct 21 ms 38516 KB Output is correct
8 Correct 26 ms 38476 KB Output is correct
9 Correct 26 ms 38484 KB Output is correct
10 Correct 23 ms 38484 KB Output is correct
11 Correct 19 ms 37952 KB Output is correct
12 Correct 21 ms 38536 KB Output is correct

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 38484 KB Output is correct
2 Correct 22 ms 38536 KB Output is correct
3 Correct 25 ms 38484 KB Output is correct
4 Correct 21 ms 38444 KB Output is correct
5 Correct 21 ms 38512 KB Output is correct
6 Correct 21 ms 38456 KB Output is correct
7 Correct 21 ms 38516 KB Output is correct
8 Correct 26 ms 38476 KB Output is correct
9 Correct 26 ms 38484 KB Output is correct
10 Correct 23 ms 38484 KB Output is correct
11 Correct 19 ms 37952 KB Output is correct
12 Correct 21 ms 38536 KB Output is correct
13 Correct 851 ms 124672 KB Output is correct
14 Correct 881 ms 125540 KB Output is correct
15 Correct 767 ms 124992 KB Output is correct
16 Correct 768 ms 124720 KB Output is correct
17 Correct 847 ms 124940 KB Output is correct
18 Correct 946 ms 126140 KB Output is correct
19 Correct 872 ms 127876 KB Output is correct
20 Correct 907 ms 128312 KB Output is correct
21 Correct 791 ms 126336 KB Output is correct
22 Correct 855 ms 128980 KB Output is correct
23 Incorrect 76 ms 46692 KB Output isn't correct
24 Halted 0 ms 0 KB -