oj.uz

Submission #482799

# Submission time Handle Problem Language Result Execution time Memory
482799 2021-10-26T11:42:34 Z CSQ31 3D Histogram (COCI20_histogram) C++17
110 / 110
 1093 ms 215296 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));
	}	
}
void solve(int l,int r){
	if(r-l<=1){
		ans = max(ans,b[l] * 1LL * a[l]);
		ans = max(ans,b[r] * 1LL * a[r]);
		ans = max(ans,min(b[l],b[r]) * 1LL * min(a[l],a[r]) * 1LL *2);
		return;
	}
	int m = (l+r)/2;
	solve(l,m);
	solve(m,r);
	f[m] = a[m];g[m] = b[m];
	for(int i=m-1;i>=l;i--)f[i] = min(a[i],f[i+1]);
	for(int i=m+1;i<=r;i++)f[i] = min(a[i],f[i-1]);
	
	for(int i=m+1;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;
	if(debug){
		cout<<"at "<<l<<" "<<m<<" "<<r<<'\n';
		cout<<"////////////////"<<'\n';
		for(int i=1;i<=n;i++)cout<<a[i]<<" ";
		cout<<'\n';
		for(int i=1;i<=n;i++)cout<<f[i]<<" ";
		cout<<'\n';
		for(int i=1;i<=n;i++)cout<<g[i]<<" ";
		cout<<'\n';
		cout<<"///////////////"<<'\n';
	}
	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(debug){
			cout<<i<<" "<<m<<" "<<r<<" "<<pg<<" "<<pf<<'\n';
		}
		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);
	solve(1,n);
	cout<<ans;
}
/*
13
913858 839924
806286 294915
565428 723951
995885 309497
766133 520675
211717 925495
603960 934575
908711 819343
392468 734121
839916 579960
770434 574444
433131 861816
861091 408456
7 12
1352705326752
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 188300 KB Output is correct
2 Correct 114 ms 188432 KB Output is correct
3 Correct 108 ms 188372 KB Output is correct
4 Correct 106 ms 188348 KB Output is correct
5 Correct 100 ms 188336 KB Output is correct
6 Correct 135 ms 188388 KB Output is correct
7 Correct 102 ms 188324 KB Output is correct
8 Correct 97 ms 188364 KB Output is correct
9 Correct 99 ms 188428 KB Output is correct
10 Correct 96 ms 188356 KB Output is correct
11 Correct 108 ms 188168 KB Output is correct
12 Correct 103 ms 188288 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 188300 KB Output is correct
2 Correct 114 ms 188432 KB Output is correct
3 Correct 108 ms 188372 KB Output is correct
4 Correct 106 ms 188348 KB Output is correct
5 Correct 100 ms 188336 KB Output is correct
6 Correct 135 ms 188388 KB Output is correct
7 Correct 102 ms 188324 KB Output is correct
8 Correct 97 ms 188364 KB Output is correct
9 Correct 99 ms 188428 KB Output is correct
10 Correct 96 ms 188356 KB Output is correct
11 Correct 108 ms 188168 KB Output is correct
12 Correct 103 ms 188288 KB Output is correct
13 Correct 826 ms 207764 KB Output is correct
14 Correct 931 ms 212472 KB Output is correct
15 Correct 885 ms 206456 KB Output is correct
16 Correct 892 ms 206468 KB Output is correct
17 Correct 873 ms 209240 KB Output is correct
18 Correct 1020 ms 214112 KB Output is correct
19 Correct 1018 ms 213536 KB Output is correct
20 Correct 1093 ms 215296 KB Output is correct
21 Correct 810 ms 206552 KB Output is correct
22 Correct 965 ms 209348 KB Output is correct
23 Correct 161 ms 190020 KB Output is correct
24 Correct 993 ms 203848 KB Output is correct