oj.uz

Submission #445391

# Submission time Handle Problem Language Result Execution time Memory
445391 2021-07-17T20:46:56 Z grt 3D Histogram (COCI20_histogram) C++17
20 / 110
 2500 ms 38840 KB 
#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back
 
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
 
const int nax = 200 * 1000 + 10;
int n;
int a[nax], b[nax], f[nax], g[nax];
pair<ll, ll> lines[nax];
ll ans;
vector<pair<ll, ll>>T[(1 << 19)];
int R;
 
long double intersect(pair<ll,ll>&x, pair<ll,ll>&y) {
	return (long double)(y.ND - x.ND) / (x.ST  - y.ST);
}
 
void construct(int l, int r) {
	for(int i = l; i <= r; ++i) {
		T[i + R].resize(1);
		T[i + R][0] = lines[i];
	}
	l += R; r += R;
	int memol = l, memor = r;
	while(l/2 > 0) {
		l >>= 1; r >>= 1;
		for(int i = l; i <= r; ++i) {
			int &v = i;
			T[v].clear();
			for(auto x : T[(v<<1)^1]) {
				T[v].PB(x);
			}
			for(auto x : T[(v<<1)]) {
				T[v].PB(x);
			}
		}
	}
	l = memol; r = memor;
	while(l/2 > 0) {
		l >>= 1; r >>= 1;
		for(int i = l; i <= r; ++i) {
			int &v = i;
			vector<pair<ll,ll>>nw = {};
			for(auto x : T[v]) {
				if((int)nw.size() == 0) {
					nw.PB(x);
					continue;
				}
				if(nw.back().ST == x.ST) continue;
				while((int)nw.size() >= 2 && intersect(nw.back(), x) <= intersect(nw.back(), nw[(int)nw.size() - 2])) {
					nw.pop_back();
				}
				nw.PB(x);
			}
			T[v].swap(nw);
		}
	}
}
 
ll get_mx(vector<pair<ll,ll>>&vec, int x) {
	while((int)vec.size() >= 2 && vec.back().ST * x + vec.back().ND <= vec[(int)vec.size() - 2].ST * x + vec[(int)vec.size() - 2].ND) {
		vec.pop_back();
	}
	return vec.back().ST * x + vec.back().ND;
}
 
ll ask(int l, int r, int x) {
	l += R; r += R;
	ll w = max(get_mx(T[l], x), get_mx(T[r], x));
	while((l>>1) != (r>>1)) {
		if((l&1)==0) w = max(w, get_mx(T[l^1], x));
		if(r&1) w = max(w, get_mx(T[r^1], x));
		l >>= 1;
		r >>= 1;
	}
	return w;
}
 
void rec(int l, int r) {
	int mid = ((l + r) >> 1);
	if(l <= mid - 1) rec(l, mid - 1);
	if(mid + 1 <= r) rec(mid + 1, r);
	f[mid] = a[mid];
	g[mid] = b[mid];
	lines[mid] = {g[mid], (ll)g[mid] * mid};
	for(int i = mid - 1; i >= l; --i) {
		f[i] = min(f[i + 1], a[i]);
		g[i] = min(g[i + 1], b[i]);
		lines[i] = {g[i], (ll)g[i] * (-i + 1)};
	}
	for(int i = mid + 1; i <= r; ++i) {
		f[i] = min(f[i - 1], a[i]);
		g[i] = min(g[i - 1], b[i]);
		lines[i] = {g[i], (ll)g[i] * i};
	}
	construct(mid, r);
	lines[mid] = {g[mid], (ll)g[mid] * (-mid + 1)};
	int lp, rp, l2, r2;
	rp = r;
	for(lp = l; lp <= mid; ++lp) {
		while(rp >= mid && (f[lp] > f[rp] || g[lp] > g[rp])) {
			rp--;
		}
		if(rp >= mid) {
			ans = max(ans, (ll)f[lp] * g[lp] * (rp - lp + 1));
		}
	}
	lp = l;
	for(rp = r; rp >= mid; rp--) {
		while(lp <= mid && (f[rp] > f[lp] || g[rp] > g[lp])) {
			lp++;
		}
		if(lp <= mid) {
			ans = max(ans, (ll)f[rp] * g[rp] * (rp - lp + 1));
		}
	}
	rp = r;
	r2 = r;
	for(lp = l; lp <= mid; lp++) {
		while(rp >= mid && (f[lp] > f[rp])) {
			rp--;
			// erase
		}
		while(r2 - 1 >= mid && (g[lp] >= g[r2 - 1])) {
			r2--;
			// add
		}
		if(rp >= mid && g[lp] >= g[r2] && r2 <= rp) {
			// [r2, rp]
			ans = max(ans, ask(r2, rp, -lp + 1) * f[lp]);
		}
	}
	construct(l, mid);
	lp = l;
	l2 = l;
	for(rp = r; rp >= mid; rp--) {
		while(lp <= mid && (f[rp] > f[lp])) {
			lp++;
		}
		while(l2 + 1 <= mid && (g[rp] >= g[l2 + 1])) {
			l2++;
			// add
		}
		if(lp <= mid && g[rp] >= g[l2] && lp <= l2) {
			// [r2, rp]
			ans = max(ans, ask(lp, l2, rp) * f[rp]);
		}
	}
	
	
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
	}
	R = 1;
	while(R < n) R *= 2;
	rec(0, n - 1);
	cout << ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 13004 KB Output is correct
2 Correct 33 ms 13040 KB Output is correct
3 Correct 21 ms 12996 KB Output is correct
4 Correct 22 ms 12992 KB Output is correct
5 Correct 23 ms 13000 KB Output is correct
6 Correct 22 ms 13008 KB Output is correct
7 Correct 30 ms 12964 KB Output is correct
8 Correct 20 ms 13004 KB Output is correct
9 Correct 22 ms 13004 KB Output is correct
10 Correct 35 ms 13024 KB Output is correct
11 Correct 7 ms 12648 KB Output is correct
12 Correct 33 ms 13104 KB Output is correct

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 13004 KB Output is correct
2 Correct 33 ms 13040 KB Output is correct
3 Correct 21 ms 12996 KB Output is correct
4 Correct 22 ms 12992 KB Output is correct
5 Correct 23 ms 13000 KB Output is correct
6 Correct 22 ms 13008 KB Output is correct
7 Correct 30 ms 12964 KB Output is correct
8 Correct 20 ms 13004 KB Output is correct
9 Correct 22 ms 13004 KB Output is correct
10 Correct 35 ms 13024 KB Output is correct
11 Correct 7 ms 12648 KB Output is correct
12 Correct 33 ms 13104 KB Output is correct
13 Execution timed out 2585 ms 38840 KB Time limit exceeded
14 Halted 0 ms 0 KB -