Submission #476325

#	Time	Username	Problem	Language	Result	Execution time	Memory
476325		Mackerel_Pike	3D Histogram (COCI20_histogram)	C++14	0 / 110	1 ms	708 KiB

histogram

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
typedef long long ll;
ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return f*x;
}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void umin(int& a,int t){if(a>t)a=t;}
bool umax(ll& a,ll t){if(a<t)return a=t,1;return 0;}
#define MAXN 200011
#define from(u) for(int i=last[u],v=e[i].v;i;i=e[i].nxt,v=e[i].v)
int a[MAXN],b[MAXN];
struct ST
{
    int minv[20][MAXN],lg[MAXN];
    void build(int* a,int n)
    {
        for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;
        for(int i=1;i<=n;++i)minv[0][i]=a[i];
        for(int i=1;i<=lg[n];++i)
            for(int j=1;j+(1<<i)-1<=n;++j)
                minv[i][j]=min(minv[i-1][j],minv[i-1][j+(1<<(i-1))]);
    }
    int Qmin(int l,int r)
    {
        int k=lg[r-l];
        return min(minv[k][l],minv[k][r-(1<<k)+1]);
    }
}Ta,Tb;
ll ans=0;
void solve(int l,int r,int kl,int kr)
{
    int mid=(l+r)>>1;
    ll f=0;
    int pos=kl;
    for(int p=kl;p<=min(mid,kr);++p)
    {
        if(umax(f,ll(Ta.Qmin(p,mid))*Tb.Qmin(p,mid)*(mid-p+1)))
        {
            pos=p;
        }
    }
    umax(ans,f);
    if(l<mid)solve(l,mid-1,kl,pos);
    if(mid<r)solve(mid+1,r,pos,kr);
}
namespace Brute
{
    void solve(int n)
    {
    ll ans=0;
    int pre=0;
    for(int s=1;s<=n;++s)
    {
        int mina=a[s],minb=b[s];
        ll f=0,bestpos=s;
        for(int t=s;t;--t)
        {
            umin(mina,a[t]),umin(minb,b[t]);
            if(umax(f,ll(mina)*minb*(s-t+1)))bestpos=t;
        }
        umax(ans,f);
        pre=bestpos;
    }
    printf("%lld\n",ans);
    }
}
int main()
{
    int n=read();
    for(int i=1;i<=n;++i)a[i]=read(),b[i]=read();
    Ta.build(a,n),Tb.build(b,n);
    solve(1,n,1,n);
    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

histogram.cpp: In function 'void Brute::solve(int)':
histogram.cpp:60:9: warning: variable 'pre' set but not used [-Wunused-but-set-variable]
   60 |     int pre=0;
      |         ^~~

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