oj.uz

Submission #482800

# Submission time Handle Problem Language Result Execution time Memory
482800 2021-10-26T11:57:17 Z CSQ31 3D Histogram (COCI20_histogram) C++17
110 / 110
 1020 ms 214884 KB 
#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);}
bool debug = 0;
const int MAXN = 2000005;
int a[MAXN],b[MAXN],f[MAXN],g[MAXN],n;
ll ans = 0;
ll d(ll a, ll b){
	assert(b);
	return a / b + ((a^b) < 0 && (a%b));
}
struct line{
	ll m,c;
	ll eval(ll x){return m*x+c;}
	line(ll _m,ll _c):m(_m),c(_c){}
	line(){}
};
struct hull{
	vector<line>h;
	void add(line L){
		if(!h.empty() && L.m == h.back().m){
			h.back().c = max(h.back().c,L.c);
			return;
		}
		while(sz(h) >= 2){
			line c0 = h[sz(h)-1];
			line c1 = h[sz(h)-2];
			if(d(c0.c - c1.c , c1.m - c0.m) >= d(c0.c - L.c , L.m - c0.m))h.pop_back();
			else break;
		}
		h.pb(L);
	}
	ll query(ll x){
		if(h.empty())return 0;
		while(sz(h)>=2 && h[sz(h)-2].eval(x) >= h[sz(h)-1].eval(x))h.pop_back();
		return h[sz(h)-1].eval(x);
	}
}t[4*MAXN];
void build(int v,int l,int r,int tl,int tr){//this should be linear
	if(l>r)return;
	t[v].h.clear();
	//cout<<l<<" "<<r<<" "<<tl<<" "<<tr<<'\n';
	if(l==tl && r==tr){
		//cout<<"added "<<l<<" "<<r<<'\n';
		for(int i=r;i>=l;i--)t[v].add(line(g[i],g[i] * 1LL * i));
	}
	if(tl==tr)return;
	int tm = (tl+tr)/2;
	build(2*v,l,min(r,tm),tl,tm);
	build(2*v+1,max(tm+1,l),r,tm+1,tr);
	
}
ll query(int v,int l,int r,int tl,int tr,ll x){
	if(l>r)return 0;
	if(l==tl && r==tr)return t[v].query(x);
	else{
		int tm = (tl+tr)/2;
		return max(query(2*v,l,min(r,tm),tl,tm,x),
		           query(2*v+1,max(tm+1,l),r,tm+1,tr,x));
	}	
}
int thonk = 0;
void solve(int l,int r){
	if(l==r){
		ans = max(ans,a[l]*1LL*b[l]);
		return;
	}
	int m = (l+r-thonk)/2;
	solve(l,m);
	solve(m+1,r);
	f[m] = a[m];f[m+1] = a[m+1];
	g[m] = b[m];g[m+1] = b[m+1];
	for(int i=m-1;i>=l;i--)f[i] = min(a[i],f[i+1]);
	for(int i=m+2;i<=r;i++)f[i] = min(a[i],f[i-1]);
	
	for(int i=m+2;i<=r;i++)g[i] = min(b[i],g[i-1]);
	for(int i=m-1;i>=l;i--)g[i] = min(b[i],g[i+1]);
	int p = r;
	for(int i=l;i<=m;i++){ //f and g lie on left side
		while(p>m && (f[i] > f[p] || g[i] > g[p]))p--;
		if(p==m)break;
		ans = max(ans,f[i] * 1LL * g[i] * 1LL * (p-i+1));
	}
	/*
	for(int i=l;i<=m;i++){
		for(int j=m+1;j<=r;j++){
			ans = max(ans,min(f[i],f[j]) * 1LL * min(g[i],g[j]) * (j-i+1));	
		}
	}*/
	//f lie on left and g left on right
	//f[i]  * g[r] * (r-l+1)
	//f[i] (g[r]*(-l+1) + g[r]*r)
	
	build(1,m+1,r,1,n);
	int pf = r;
	int pg = r+1;
	for(int i=l;i<=m;i++){
		while(pf>m+1 && f[i] > f[pf])pf--; //[m+1,pf] is good
		while(pg-1>m && g[i] >= g[pg-1])pg--; //[pg,r] is good
		if(f[i] > f[pf] || g[i] < g[pg])continue;
		//for(int j=pg;j<=pf;j++)ans = max(ans,f[i] * 1LL * g[j] * (j-i+1));
		ans = max(ans,f[i] * 1LL * query(1,pg,pf,1,n,-i+1)); 
	}
}
int main(){
	owo
	//freopen("histogram.in.2a","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
	solve(1,n);
	reverse(a+1,a+n+1);
	reverse(b+1,b+n+1);
	thonk = 1;
	solve(1,n);
	cout<<ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 188368 KB Output is correct
2 Correct 106 ms 188404 KB Output is correct
3 Correct 98 ms 188356 KB Output is correct
4 Correct 96 ms 188292 KB Output is correct
5 Correct 104 ms 188360 KB Output is correct
6 Correct 109 ms 188472 KB Output is correct
7 Correct 106 ms 188420 KB Output is correct
8 Correct 117 ms 188376 KB Output is correct
9 Correct 99 ms 188312 KB Output is correct
10 Correct 109 ms 188284 KB Output is correct
11 Correct 122 ms 188132 KB Output is correct
12 Correct 128 ms 188400 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 188368 KB Output is correct
2 Correct 106 ms 188404 KB Output is correct
3 Correct 98 ms 188356 KB Output is correct
4 Correct 96 ms 188292 KB Output is correct
5 Correct 104 ms 188360 KB Output is correct
6 Correct 109 ms 188472 KB Output is correct
7 Correct 106 ms 188420 KB Output is correct
8 Correct 117 ms 188376 KB Output is correct
9 Correct 99 ms 188312 KB Output is correct
10 Correct 109 ms 188284 KB Output is correct
11 Correct 122 ms 188132 KB Output is correct
12 Correct 128 ms 188400 KB Output is correct
13 Correct 733 ms 208720 KB Output is correct
14 Correct 739 ms 211556 KB Output is correct
15 Correct 720 ms 207264 KB Output is correct
16 Correct 686 ms 207308 KB Output is correct
17 Correct 710 ms 210060 KB Output is correct
18 Correct 894 ms 213760 KB Output is correct
19 Correct 870 ms 213500 KB Output is correct
20 Correct 870 ms 214884 KB Output is correct
21 Correct 718 ms 207376 KB Output is correct
22 Correct 790 ms 210036 KB Output is correct
23 Correct 148 ms 190284 KB Output is correct
24 Correct 1020 ms 206492 KB Output is correct