제출 #1159822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159822		jmuzhen	3D Histogram (COCI20_histogram)	C++20	20 / 110	2596 ms	68888 KiB

histogram

//GrabFood

#include<bits/stdc++.h>
using namespace std;
#define int long long
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(int s[]) {
		for (int i = 2; i <= n; i++) lg[i]=lg[i>>1]+1;
		for (int i = 0; i < n; i++) st[i][0] = s[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);
}
	

signed 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;
	
	ST* s1 = new ST(a.data());
	ST* s2 = new ST(b.data());
	
	for (int i = 0; i <n ;i++) {
		for(int j =i;j<n;j++) {
			ans=max(ans, (j-i+1)*(s1->query(i,j))*(s2->query(i,j)));
		}
	}
	
	cout << ans << endl;
	
}

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