Submission #639955

#	Time	Username	Problem	Language	Result	Execution time	Memory
639955		vladislav11	사탕 분배 (IOI21_candies)	C++17	0 / 100	181 ms	101888 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct SegTree
{
    vector<ll> tree, padd, righ, mini, maxi;
    
    void init ( int s )
    {
        tree = padd = righ = mini = maxi = vector<ll>( 4*s, 0 );
    }
    
    void ppush ( int v, int tl, int tr )
    {
        tree[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 )
    {
        tree[v] = tree[2*v] + tree[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, int 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);
    }
    
    int fnd ( int v, int tl, int tr, ll x, ll cmin, ll cmax )
    {
        ppush( v, tl, tr );
        
        if ( max( maxi[v], cmax ) - min( mini[v], cmin ) <= x )
            return tl;
        
        int mid = ( tl + tr ) / 2;
        
        if ( max( maxi[2*v+1], cmax ) - min( mini[2*v+1], cmin ) > x )
            return fnd( 2*v+1, mid+1, tr, x, cmin, cmax );
        
        if ( max({ maxi[2*v+1], righ[2*v], cmax }) - min({ mini[2*v+1], righ[2*v], cmin }) <= x )
            return fnd( 2*v, tl, mid, x, min( cmin, mini[2*v+1] ), max( cmax, maxi[2*v+1] ) );
        
        return fnd( 2*v+1, mid+1, tr, x, cmin, cmax );
    }
    
    ll tget ( int v, int tl, int tr, int pos )
    {
        ppush( v, tl, tr );
        
        if ( tl == tr )
            return tree[v];
        
        int mid = ( tl + tr ) / 2;
        
        if ( pos <= mid )
            return tget( 2*v, tl, mid, pos );
        
        return tget( 2*v+1, mid+1, tr, pos );
    }
    
    ll tfnc ( int v, int tl, int tr, int l, int r, bool bmin )
    {
        ppush( v, tl, tr );
        
        if ( tr < l || r < tl )
            return bmin ? 2e18 : -2e18;
        
        if ( l <= tl && tr <= r )
            return bmin ? mini[v] : maxi[v];
        
        int mid = ( tl + tr ) / 2;
        
        if ( bmin )
            return min( tfnc( 2*v, tl, mid, l, r, true ), tfnc( 2*v+1, mid+1, tr, l, r, true ) );
        
        return max( tfnc( 2*v, tl, mid, l, r, false ), tfnc( 2*v+1, mid+1, tr, l, r, false ) );
    }
}
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] });
    }
    
    stree.init(m+1);
    
    vector<int> ans(n);
    
    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 endval = stree.tget( 1, 0, m, m );
        
        if ( p == 0 )
            ans[i] = endval;
        else
        {
            ll x = stree.tget( 1, 0, m, p-1 );
            
            ll mini = stree.tfnc( 1, 0, m, p, m, true );
            ll maxi = stree.tfnc( 1, 0, m, p, m, false );
            
            if ( x < mini )
                ans[i] = endval - ( maxi - c[i] );
            else
                ans[i] = endval - mini;
        }
    }
    
    return ans;
}

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