oj.uz

Submission #476325

# Submission time Handle Problem Language Result Execution time Memory
476325 2021-09-26T03:50:03 Z Mackerel_Pike 3D Histogram (COCI20_histogram) C++14
0 / 110
 1 ms 708 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 708 KB Output is correct
11 Incorrect 0 ms 332 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 708 KB Output is correct
11 Incorrect 0 ms 332 KB Output isn't correct
12 Halted 0 ms 0 KB -