Submission #640176

#	Time	Username	Problem	Language	Result	Execution time	Memory
640176		vladislav11	Distributing Candies (IOI21_candies)	C++17	0 / 100	169 ms	94036 KiB

candies

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct SegTree
{
    vector<ll> /*sum,*/ padd, righ, mini, maxi;
    
    void init ( int s )
    {
        /*sum = */padd = righ = mini = maxi = vector<ll>( 4*s, 0 );
    }
    
    void ppush ( int v, int tl, int tr )
    {
        //sum[v] += (tr-tl+1)*padd[v];
        righ[v] += padd[v];
        mini[v] += padd[v];
        maxi[v] += padd[v];
        
        if ( tl != tr )
        {
            padd[2*v] += padd[v];
            padd[2*v+1] += padd[v];
        }
        
        padd[v] = 0;
    }
    
    void upd ( int v )
    {
        //sum[v] = sum[2*v] + sum[2*v+1];
        righ[v] = righ[2*v+1];
        mini[v] = min( mini[2*v], mini[2*v+1] );
        maxi[v] = max( maxi[2*v], maxi[2*v+1] );
    }
    
    void tadd ( int v, int tl, int tr, int l, int r, ll x )
    {
        ppush( v, tl, tr );
        
        if ( tr < l || r < tl )
            return;
        
        if ( l <= tl && tr <= r )
        {
            padd[v] += x;
            ppush( v, tl, tr );
            return;
        }
        
        int mid = ( tl + tr ) / 2;
        
        tadd( 2*v, tl, mid, l, r, x );
        tadd( 2*v+1, mid+1, tr, l, r, x );
        
        upd( v );
    }
    
    ll tget ( int v, int tl, int tr, int pos )
    {
        ppush( v, tl, tr );
        
        if ( tl == tr )
            return righ[v];
        
        int mid = ( tl + tr ) / 2;
        
        return pos <= mid ? tget( 2*v, tl, mid, pos ) : tget( 2*v+1, mid+1, tr, pos );
    }
    
    ll tfun ( int v, int tl, int tr, int l, int r, bool tmin )
    {
        ppush( v, tl, tr );
        
        if ( tr < l || r < tl )
            return tmin ? 1e18 : -1e18;
        
        if ( l <= tl && tr <= r )
            return tmin ? mini[v] : maxi[v];
        
        int mid = ( tl + tr ) / 2;
        
        if ( tmin )
            return min( tfun( 2*v, tl, mid, l, r, true ), tfun( 2*v+1, mid+1, tr, l, r, true ) );
        
        return max( tfun( 2*v, tl, mid, l, r, false ), tfun( 2*v+1, mid+1, tr, l, r, false ) );
    }
    
    int fnd ( int v, int tl, int tr, ll x, ll tmin, ll tmax )
    {
        ppush( v, tl, tr );
        
        if ( max( maxi[v], tmax ) - min( mini[v], tmin ) <= x ) /// ?
            return tl;
        
        int mid = ( tl + tr ) / 2;
        
        if ( max( maxi[2*v+1], tmax ) - min( mini[2*v+1], tmin ) > x )
            return fnd( 2*v+1, mid+1, tr, x, tmin, tmax );
    
        if ( max({ maxi[2*v+1], tmax, righ[2*v] }) - min({ mini[2*v+1], tmin, righ[2*v] }) <= x )
            return fnd( 2*v, tl, mid, x, min( tmin, mini[2*v+1] ), max( tmax, maxi[2*v+1] ) );
        
        return fnd( 2*v+1, mid+1, tr, x, tmin, tmax );
    }
}
stree;

vector<int> distribute_candies( vector<int> c, vector<int> l, vector<int> r, vector<int> v )
{
    int n = c.size();
    int m = v.size();
    
    vector< vector< pair<int,int> > > event( n+1 );
    
    for ( int i=0; i<m; i++ )
    {
        event[ l[i] ].push_back({ i+1, v[i] });
        event[ r[i]+1 ].push_back({ i+1, -v[i] });
    }
    
    vector<int> ans(n);
    
    stree.init( m+1 );
    
    for ( int i=0; i<n; i++ )
    {
        for ( auto& [ind,delt] : event[i] )
            stree.tadd( 1, 0, m, ind, m, delt );
        
        int p = stree.fnd( 1, 0, m, c[i], 1e18, -1e18 );
        
        ll last_val = stree.tget( 1, 0, m, m );
        
        if ( p == 0 )
            ans[i] = last_val;
        else
        {
            ll x = stree.tget( 1, 0, m, p-1 );
            
            ll mini = stree.tfun( 1, 0, m, p, m, true );
            ll maxi = stree.tfun( 1, 0, m, p, m, false );
            
            if ( x < mini )
                ans[i] = last_val - ( maxi - c[i] );
            else
                ans[i] = last_val - mini;
        }
    }
    
    return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33