Submission #467225

#	Time	Username	Problem	Language	Result	Execution time	Memory
467225		JvThunder	Distributing Candies (IOI21_candies)	C++17	100 / 100	489 ms	35188 KiB

candies

#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
using namespace std;

const ll INF = (ll)(1e18);

// make a segtree where each leaf represents
struct segtree
{
    vector<ll> smx, smn, sum; 
    int N;
    segtree()
    {
        N = 1<<18;
        smx.assign(2*N,0); // suffix max
        smn.assign(2*N,0); // suffix min
        sum.assign(2*N,0); // range sum
    }

    void upd(ll v, int t, int node, int lx, int rx) // updates val v into position t 
    {
	    if(rx-lx==1) 
        {
            // set leaf to v
            smx[node] = max(0LL, v);
            smn[node] = min(0LL, v);
            sum[node] = v;
            return;
        }
 
        int mid = (lx+rx)/2;
        if(t<mid) upd(v, t, 2*node, lx, mid);
        else upd(v, t, 2*node+1, mid, rx);
        
        // change values after update
        sum[node] = sum[2*node]+sum[2*node+1];
        smx[node] = max(smx[2*node],sum[2*node]+smx[2*node+1]);
        smn[node] = min(smn[2*node],sum[2*node]+smn[2*node+1]);
        return;
    }
    
    // return the sum of the suffix of the last index smx-smn>c 
    ll get(ll c,int node, int lx, int rx) 
    {
        if(rx-lx==1) return min(max(sum[node], 0LL), c);
    
        int mid = (lx+rx)/2;

        // binary search last index smx-smn>c    
        // if found in right side, directly go right
        if(smx[2*node+1]-smn[2*node+1]>c) return get(c, 2*node+1, mid, rx);
        
        // else go left
        ll a = get(c, 2*node, lx, mid);
        // guarantees no touching the bottom
        if(a+smx[2*node+1]>c) return c-(smx[2*node+1]-sum[2*node+1]);
        // guarantees no touching the top
        if(a+smn[2*node+1]<0) return 0+(sum[2*node+1]-smn[2*node+1]);
        // guarantees no touching both
        return a+sum[2*node+1];
    }

} st;
 
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) 
{
	int n=c.size(), q=l.size();
	vector<int> final_A; // final array
	vector<vector<int>> upd(n+1); // upd[i] store update at pos i

    // positive or negative to show left or right
	for (int i=1; i<=q; i++) upd[l[i-1]].pb(i), upd[r[i-1]+1].pb(-i); 
	for (int i=0; i<n; i++) 
    {
		for (auto j:upd[i]) 
        {
            // j is the index of query
			if (j>0) st.upd(v[j-1], j-1, 1, 0, q);
			else st.upd(0, -j-1, 1, 0, q); // set back pos x to 0
		}
		final_A.pb(st.get(c[i], 1, 0, q));
	}
	return final_A;
}

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