Submission #1217105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217105		thunopro	3D Histogram (COCI20_histogram)	C++20	0 / 110	1 ms	320 KiB

histogram

#include<bits/stdc++.h>
using namespace std ; 
#define int long long 
#define maxn 200009
#define ll long long 
#define pb push_back 
#define fi first 
#define se second 
#define left id<<1
#define right id<<1|1 
#define re exit(0); 
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1 
#define TIME ( 1.0*clock() / CLOCKS_PER_SEC )
const int mod = 1e9+7 ;
const ll INF = 1e18; 

typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 

template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } 
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } 

void add ( int &a , int b ) 
{
    a += b ; 
    if ( a >= mod ) a -= mod ; 
    if ( a < 0 ) a += mod ; 
}

void rf () 
{
#ifndef ONLINE_JUDGE
freopen("bai1.inp","r",stdin);
freopen ("bai1.out","w",stdout) ;
#endif
}

int _pow ( int a , int n ) 
{
    if ( n == 0 ) return 1 ; 
    int res = _pow (a,n/2) ; 
    if ( n % 2 ) return 1ll*res*res%mod*a%mod ; 
    else return 1ll*res*res%mod ; 
}

int n ; 
int a [maxn] , b [maxn] ; 
ll res = 0 ; 

struct Line 
{
    int m , b ; 
    int eval ( int x ) 
    {
        return m*x + b ; 
    }
    long double intersect ( Line l ) 
    {
        return ((long double) l.b - b ) / ( m -l.m ) ; 
    }
}; 

struct Hull{
    deque <Line> dq ; 
    void add_line ( Line l ) 
    {
        if ( dq.size () && dq [0].b >= l.b ) return ; 
        if ( dq.size () && dq [0].m == l.m ) 
        {
            l.m = max (l.m,dq [0].m) ; 
            dq.pop_front() ; 
        }

        while (dq.size() >= 2 && dq [0].intersect(dq[1]) <= dq [1].intersect(l)) dq.pop_front() ; 

        dq.push_front(l) ; 
    }
    int query ( int x ) 
    {
        if ( dq.empty() ) return - INF ; 
        while (dq.size () >= 2 && dq [0].intersect(dq[1]) < x ) dq.pop_front() ; 
        return dq[0].eval(x) ; 
    }
}; 

void calc ( vii L , vii R ) 
{
    int N = R.size () ; 
    vector<Hull> bit (N+1) ; 
    auto add_bitline = [&] ( int p , Line l ) 
    {
        p = N - p ; 
        for ( int i = p ; i <= N ; i += (i&-i)) bit [i].add_line(l) ; 
    }; 
    auto query = [&] ( int p , int x ) 
    {
        p = N - p ; 
        int res = 0 ; 
        for ( int i = p ; i > 0 ; i -= (i&-i)) chkmax (res,bit[i].query(x)) ; 
        return res ; 
    }; 

    int p1 = 0 , p2 = 0 ; 
    int cnt = 0 ; 

    for ( auto x : L ) 
    {
        while ( p1 < R.size () && R[p1].fi >= x.fi && R[p1].se >= x.se ) p1 ++ ; 
        while ( p2 < R.size () && R[p2].fi >= x.fi ) 
        {
            add_bitline (p2,{R[p2].se,R[p2].se*(p2+1)}) ; 
            p2 ++ ; 
        }
        cnt ++ ; 
        chkmax (res,x.fi*x.se*(cnt+p1)) ; 

        int best = query (p1,cnt) ; 
        if ( best > 0 ) chkmax (res,x.fi*best) ; 
    }
}
void solve ( int l , int r ) 
{
    if ( l > r ) return ; 
    if ( l == r ) 
    {
        chkmax (res,a[l]*b[l]) ; 
        return ; 
    }
    int mid = (l+r)/2 ; 
    solve (l,mid) ; solve (mid+1,r) ; 
    vii L,R ; 
    int minA = INF , minB = INF ;
    for ( int i = mid + 1 ; i <= r ; i ++ ) 
    {
        chkmin (minA,a[i]) ; 
        chkmin (minB,b[i]) ; 
        R . pb({minA,minB}) ; 
    }
    minA = INF , minB = INF ; 
    for ( int i = mid ; i >= l ; i -- ) 
    {
        chkmin (minA,a[i]) ; 
        chkmin (minB,b[i]) ; 
        L . pb ({minA,minB}) ; 
    }
    calc (L,R) ; 
    calc (R,L) ; 
}
signed main () 
{
    ios_base::sync_with_stdio(0); 
    cin.tie(0);cout.tie(0); 
    rf () ;
    cin >> n ; 
    for ( int i = 1 ; i <= n ; i ++ ) cin >> a [i] >> b [i]; 
    res = 0 ; 
    solve (1,n) ; 
    cout << res ; 
    return 0;
}

Compilation message (stderr)

histogram.cpp: In function 'void rf()':
histogram.cpp:34:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 | freopen("bai1.inp","r",stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
histogram.cpp:35:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | freopen ("bai1.out","w",stdout) ;
      | ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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