Submission #1159808

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

histogram

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

using ll = 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]);
	}
	
};

vector<ll> seg(N*4, 1e9);
void update(int idx, int l, int r, int pos, ll val) {
	if (l==r) {
		seg[idx]=val;return;
	}
	int mid=(l+r)/2;
	if(pos<=mid)
		update(idx*2,l,mid,pos,val);
	else
		update(idx*2+1,mid+1,r,pos,val);
	seg[idx]=min(seg[idx*2],seg[idx*2+1]);
}
// idx of first element in [l,r] <=b
// default to -1
int query_first(int idx,int l, int r, ll b) {
	if (seg[idx]>b) return -1;
	if(l==r)return l;
	int mid=(l+r)/2;
	if(seg[idx*2]<=b)
		return query_first(idx*2,l,mid,b);
	else
		return query_first(idx*2+1,mid+1,r,b);
}
	

int main() {
	cin>>n;

	for (int i = 0; i < n; i++) {
		cin>>a[i];
		cin>>b[i];
		update(1, 1, n, i+1, a[i]); // 1-indexed
	}
	
	int ans = 0;
	int cur = 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();
			// what is the maximum width that we can use block x?
			int qf = query_first(1, 1, n, a[x]-1) - 1;
			if (qf>x)qf=-1;
			if(DEBUG) cout<<"qf: " << x+1 << " , " << a[x] << " , " <<qf<<endl;
			int L = min(x, qf<0 ? 0 : qf+1); // incorrect, we can go earlier as well.
			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;
		}
		
		st.push_back(i);
		
	}
	
	cout << ans << endl;
	
}

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