Submission #503092

#	Time	Username	Problem	Language	Result	Execution time	Memory
503092		maomao90	3D Histogram (COCI20_histogram)	C++17	0 / 110	14 ms	13860 KiB

histogram

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end() 
#define sz(x) (int) (x).size()
#define m first
#define c second
#define show(x) cerr << #x << " is " << x << endl;
typedef long long lint;
typedef long double lida;
typedef pair<lint,lint> line;

lint eval(line L, lint x){ return L.m * x + L.c; }
lida cross(line a, line b){ return (lida) (a.c-b.c) / (lida) (b.m-a.m); }

struct convexhull{
	vector<line> hull;
	void addline(line L){
		if(hull.empty() or hull.back().m != L.m) hull.push_back(L);
		else hull.back().c = max(hull.back().c, L.c);
		while(sz(hull) >= 3){
			int S = sz(hull);
			if(cross(hull[S-3], hull[S-1]) < cross(hull[S-2], hull[S-3])){
				hull[S-2] = hull[S-1];
				hull.pop_back();
			}
			else break;
		}
	}
	lint query(lint x){
		if(hull.empty()) return 0;
		while(sz(hull) >= 2){
			if(eval(hull[sz(hull)-2],x) > eval(hull[sz(hull)-1], x)) hull.pop_back();
			else break;
		}
		return eval(hull.back(), x);
	}
	void clear(){ hull.clear(); }
};

lint ans = 0;
lint a[200005], b[200005], A[200005], B[200005]; ///A,B are raw value. a,b are for the prefix/suffix min
int n;

int dis[1000005];
int N = 200002;
convexhull seg[400005];

void update(line L, int i){
	for(i += N;i > 0;i >>= 1) seg[i].addline(L);
}
void reset(int i){
	for(i += N;i > 0;i >>= 1) seg[i].clear();
}
lint query(int l, int r, lint x){
	lint res = 0;
	for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
		if(l&1) res = max(res, seg[l++].query(x));
		if(r&1) res = max(res, seg[--r].query(x));
	}
	return res;
}

void dnc(int s, int e){
	if(s == e){
		ans = max(ans, A[s]*B[s]);
		return;
	}
	int m = (s+e)/2;
	dnc(s,m); dnc(m+1,e);
	
	a[m] = A[m], b[m] = B[m], a[m+1] = A[m+1], b[m+1] = B[m+1];
	for(int i = m-1;i >= s;i--){
		a[i] = min(a[i+1], A[i]);
		b[i] = min(b[i+1], B[i]);
	}
	for(int i = m+2;i <= e;i++){
		a[i] = min(a[i-1], A[i]);
		b[i] = min(b[i-1], B[i]);
	} 
		
	///a, b both on left side
	int r = e;
	for(int l = s;l <= m;l++){
		while(r >= m+1){
			if(a[l] > a[r] or b[l] > b[r]) r--;
			else break;
		}
		if(r == m) break;
		ans = max(ans, (r-l+1) * a[l] * b[l]);
	}

	///a on left and b on right
	r = e;
	for(int l = s;l <= m;l++){
		while(r >= m+1){
			if(a[l] >= a[r]){
				update(line(a[r], (r+1)*a[r]), dis[b[r]]); ///a[r] increasing going to the left
				r--;
			}
			else break;
		}
		lint res = query(dis[b[l]], N-1, -l); ///-l decreasing going to the right
		res *= b[l];
		ans = max(ans, res);
	}
	for(int r = m+1;r <= e;r++) reset(dis[b[r]]);	
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> A[i] >> B[i];
	
	for(int i = 1;i <= n;i++) dis[B[i]] = 1;
	for(int i = 1;i <= 1000000;i++) dis[i] += dis[i-1];
	
	dnc(1, n);
	reverse(A+1,A+n+1);
	reverse(B+1,B+n+1);
	dnc(1, n);
		
	cout << ans;
}

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