Submission #480924

#	Time	Username	Problem	Language	Result	Execution time	Memory
480924		CSQ31	3D Histogram (COCI20_histogram)	C++17	20 / 110	2582 ms	5364 KiB

histogram

#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
//this problem boils down to solving range queries for 2D histograms
//offline d&c
//we want to solve for queries that have L<=M and R>M
//sort by L first ,we can define prof[R+i] as the max profit if we choose border at R+i
//update R incrementally
//but this should be n * log^2n?
//should barely pass TL
const int MAXN = 2000001;
int al[MAXN],ar[MAXN],bl[MAXN],br[MAXN],a[MAXN],b[MAXN],n;
stack<pii>stk;
void mono(int *l,int *aa,bool mode){
	while(!stk.empty())stk.pop();
	if(!mode){
		for(int i=1;i<=n;i++){
			while(!stk.empty() && stk.top().fi  >= aa[i])stk.pop();
			if(stk.empty())l[i] = 0;
			else l[i] = stk.top().se;
			stk.push({aa[i],i});
		}
	}else{
		for(int i=n;i>=1;i--){
			while(!stk.empty() && stk.top().fi  >= aa[i])stk.pop();
			if(stk.empty())l[i] = n+1;
			else l[i] = stk.top().se;
			stk.push({aa[i],i});
		}
		
	}
	
}
int main(){
	owo
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
	mono(al,a,0);
	mono(bl,b,0);
	mono(ar,a,1);
	mono(br,b,1);	
	ll ans = 0;
	for(int i=1;i<=n;i++){
		int l = al[i]+1;
		int r = ar[i]-1;
		ll m = 0;
		//need to speed this part up
		for(int j=l;j<=r;j++){
			m = max(m,b[j] *1LL * (min(br[j]-1,r) - max(bl[j]+1,l) + 1));
		}
		ans = max(ans,m * 1LL * a[i]);
	}
	cout<<ans<<'\n';
	
}

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