Submission #1159826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159826		jmuzhen	3D Histogram (COCI20_histogram)	C++20	0 / 110	3 ms	5188 KiB

histogram

#include<bits/stdc++.h>
using namespace std;

#define int long long

constexpr int N = 2e5+5, L = log2(N)+1;
constexpr bool DEBUG = 0;

vector<int> a(N), b(N);
int n;

// min st on vector b
struct ST {
	int st[N][L], lg[N]={0};
	ST() {
		for (int i = 2; i <= n; i++) lg[i]=lg[i>>1]+1;
		for (int i = 0; i < n; i++) st[i][0] = b[i];
		
		for (int j=1; (1<<j)<=n; j++) {
			for (int i=0; i+(1<<j)-1<n; i++) {
				st[i][j] = min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
			}
		}
	}
	
	int query(int l,int r) {
		int i = lg[r-l+1];
		return min(st[l][i], st[r-(1<<i)+1][i]);
	}
	
};

signed main() {
	cin>>n;

	for (int i = 0; i < n; i++) {
		cin>>a[i];
		cin>>b[i];
	}
	
	int ans = 0;
	
	ST* sparseTable = new ST();
	
	vector<int> st;
	
	for (int i = 0; i <= n; i++) {
		int h = i < n ? a[i] : 0;

		while (!st.empty() && a[st.back()] > h) {
			int x = st.back();
			st.pop_back();
			int L = x;
			int R = i-1;
			int width = R-L+1;
			int bwidth = sparseTable->query(L,R);
			ans = max(ans, width * a[x] * bwidth);
			if (DEBUG) cout << width << "*" << a[x] << "*" << bwidth << endl;
			
			int L2 = x;
			int R2 = i;
			int width2 = R2-L2+1;
			int bwidth2 = sparseTable->query(L2,R2);
			ans = max(ans, width2 * h * bwidth2);
			if (DEBUG) cout << width2 << "*" << h << "*" << bwidth2 << endl;
		}
		st.push_back(i);
	}
	
	cout << ans << endl;
	
}

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