Submission #501419

#	Time	Username	Problem	Language	Result	Execution time	Memory
501419		jamezzz	3D Histogram (COCI20_histogram)	C++17	110 / 110	689 ms	250368 KiB

histogram

#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));
 
#define mod 1000000007
 
inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}
 
inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}
 
inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}
 
struct node{
	int s,e,m;ll v;
	node *l,*r;
	node(int _s,int _e){
		s=_s;e=_e;m=(s+e)/2;v=0;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void up(int x,ll nv){
		if(s==x&&e==x){mxto(v,nv);return;}
		if(x<=m)l->up(x,nv);
		else r->up(x,nv);
		v=max(l->v,r->v);
	}
	ll qry(int x,int y){
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return max(l->qry(x,m),r->qry(m+1,y));
	}
}*aseg=new node(1,200005),*bseg=new node(1,200005);
 
struct line{
	ll m,c;
	line(ll _m,ll _c){m=_m;c=_c;}
	ll get(ll x){return m*x+c;}
};
 
struct lct{
	int s,e,m;
	line val=line(0,-INF);
	lct *l=nullptr,*r=nullptr;
	lct(int _s,int _e){
		s=_s;e=_e;m=(s+e)/2;
	}
	void up(line i){
		bool lo=i.get(s)>val.get(s);
		bool mi=i.get(m)>val.get(m);
		bool hi=i.get(e)>val.get(e);
		if(mi)swap(i,val);
		if(e-s==1||i.c==LINF||lo==hi)return;
		if(lo!=mi){
			if(l==nullptr)l=new lct(s,m);
			l->up(i);
		}
		else{
			if(r==nullptr)r=new lct(m,e);
			r->up(i);
		}
	}
	ll qry(ll i){
		if(s+1==e)return val.get(i);
		if(i<m&&l!=nullptr)return max(l->qry(i),val.get(i));
		else if(r!=nullptr)return max(r->qry(i),val.get(i));
		return val.get(i);
	}
};
 
#define maxn 200005
 
int n,a[maxn],b[maxn],al[maxn],ar[maxn],bl[maxn],br[maxn];
stack<int> s;
vi arange[maxn],brange[maxn];
vii aqry[maxn],bqry[maxn];
ll ans=0;
 
void dnc(int l,int r){
	if(l==r)return;
	int m=(l+r)/2;
	dnc(l,m);dnc(m+1,r);
	lct *alct=new lct(1,maxn);
	lct *blct=new lct(1,maxn);
	int ptr=sz(bqry[m+1])-1;
	for(int i=sz(aqry[l])-1;i>=0;--i){
		while(ptr>=0&&bl[bqry[m+1][ptr].se]>=al[aqry[l][i].se]){
			int j=bqry[m+1][ptr].se;
			blct->up({b[j],-(ll)(bl[j]-1)*b[j]});
			--ptr;
		}
		int j=aqry[l][i].se;
		mxto(ans,blct->qry(ar[j])*a[j]);
	}
	ptr=sz(aqry[m+1])-1;
	for(int i=sz(bqry[l])-1;i>=0;--i){
		while(ptr>=0&&al[aqry[m+1][ptr].se]>=bl[bqry[l][i].se]){
			int j=aqry[m+1][ptr].se;
			alct->up({a[j],-(ll)(al[j]-1)*a[j]});
			--ptr;
		}
		int j=bqry[l][i].se;
		mxto(ans,alct->qry(br[j])*b[j]);
	}
	
	vii tmp;
	tmp.resize(sz(aqry[l])+sz(aqry[m+1]));
	merge(all(aqry[l]),all(aqry[m+1]),tmp.begin());
	swap(tmp,aqry[l]);tmp.clear();
	tmp.resize(sz(bqry[l])+sz(bqry[m+1]));
	merge(all(bqry[l]),all(bqry[m+1]),tmp.begin());
	swap(tmp,bqry[l]);tmp.clear();
}
 
int main(){
	sf("%d",&n);
	for(int i=1;i<=n;++i){
		sf("%d%d",&a[i],&b[i]);
	}
	
	s.push(0);
	for(int i=1;i<=n;++i){
		while(!s.empty()&&a[s.top()]>=a[i])s.pop();
		al[i]=s.top()+1;
		arange[al[i]].pb(i);
		s.push(i);
	}
	while(!s.empty())s.pop();
	s.push(0);
	for(int i=1;i<=n;++i){
		while(!s.empty()&&b[s.top()]>=b[i])s.pop();
		bl[i]=s.top()+1;
		brange[bl[i]].pb(i);
		s.push(i);
	}
	while(!s.empty())s.pop();
	s.push(n+1);
	for(int i=n;i>=1;--i){
		while(!s.empty()&&a[s.top()]>=a[i])s.pop();
		ar[i]=s.top()-1;
		aqry[ar[i]].pb({al[i],i});
		s.push(i);
	}
	while(!s.empty())s.pop();
	s.push(n+1);
	for(int i=n;i>=1;--i){
		while(!s.empty()&&b[s.top()]>=b[i])s.pop();
		br[i]=s.top()-1;
		bqry[br[i]].pb({bl[i],i});
		s.push(i);
	}
	while(!s.empty())s.pop();
	
	for(int i=1;i<=n;++i){
		sort(all(aqry[i]));
		sort(all(bqry[i]));
	}
	
	for(int i=n;i>=1;--i){
		for(int j:arange[i]){
			aseg->up(ar[j],(ll)(ar[j]-al[j]+1)*a[j]);
		}
		for(int j:brange[i]){
			bseg->up(br[j],(ll)(br[j]-bl[j]+1)*b[j]);
		}
		for(int j:arange[i]){
			mxto(ans,bseg->qry(al[j],ar[j])*a[j]);
		}
		for(int j:brange[i]){
			mxto(ans,aseg->qry(bl[j],br[j])*b[j]);
		}
	}
	
	dnc(1,n);
	
	pf("%lld\n",ans);
}

Compilation message (stderr)

histogram.cpp: In function 'int main()':
histogram.cpp:159:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |  sf("%d",&n);
      |    ^
histogram.cpp:161:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |   sf("%d%d",&a[i],&b[i]);
      |     ^

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