Submission #467097

#	Time	Username	Problem	Language	Result	Execution time	Memory
467097		JvThunder	Distributing Candies (IOI21_candies)	C++17	100 / 100	469 ms	31376 KiB

candies

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

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

struct segtree
{
    vector<ll> smx, smn, sum; 
    int N;
    segtree()
    {
        N = 1<<18;
        smx.assign(2*N,0);
        smn.assign(2*N,0);
        sum.assign(2*N,0);
    }

    void upd(ll v, int t, int node, int lx, int rx) 
    {
	    if(rx-lx==1) 
        {
            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);
        
        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]);
    }
 
    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;
        if(smx[2*node+1]-smn[2*node+1]>c) return get(c, 2*node+1, mid, rx);
        ll a = get(c, 2*node, lx, mid);

        if(a+smx[2*node+1]>c) return c-(smx[2*node+1]-sum[2*node+1]);
        if(a+smn[2*node+1]<0) return sum[2*node+1]-smn[2*node+1];
        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

    // +1 to remove ambiguity of index 0 
    // positive or negative to show left or right
	for (int i=0; i<q; i++) upd[l[i]].pb(i+1), upd[r[i]+1].pb(-(i+1)); 
	for (int i=0; i<n; i++) 
    {
		for (auto j:upd[i]) 
        {
            // j is the update position
			if (j>0) --j, st.upd(v[j], j, 1, 0, q);
			else j=-j-1, st.upd(0, j, 1, 0, q);
		}
		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