Submission #1282265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282265		Faggi	사탕 분배 (IOI21_candies)	C++20	29 / 100	69 ms	11996 KiB

candies

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V)
{
    ll n=sz(C), q=sz(V), i;
    vector<ll>pref(q+1,0), ma(q+1), mi(q+1);
    for(i=1; i<=q; i++)
        pref[i]=pref[i-1]+V[i-1];
    
    ma[q]=mi[q]=pref[q];
    
    for(i=q-1; i>=0; i--)
    {
        ma[i]=max(ma[i+1],pref[i]);
        mi[i]=min(mi[i+1],pref[i]);
    }
    vector<int>ans(n);
    for(i=0; i<n; i++)
    {
        ll l=0, r=q+1, piv, pos=0;
        if(ma[0]-mi[0]<C[i])
        {
            ans[i]=pref[q]-mi[0];
            continue;
        }
        while(l<=r)
        {
            piv=(l+r)/2;
            if(ma[piv]-mi[piv]>=C[i])
            {
                l=piv+1;
                pos=piv;
            }
            else
                r=piv-1;
        }

        if(pref[pos]<pref[q])
            ans[i]=C[i]-(ma[pos]-pref[q]);
        else
            ans[i]=pref[q]-mi[pos];
    }
    return ans;
}

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