Submission #438749

#	Time	Username	Problem	Language	Result	Execution time	Memory
438749		fcmalkcin	Distributing Candies (IOI21_candies)	C++17	0 / 100	160 ms	43120 KiB

candies

#include  "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn=1e5+10;
const ll mod =998244353 ;
const ll base=3e18;
struct tk
{
    ll pmn=0,pmx=0, sum=0;
    int chk=-1;
};
tk mer(tk a, tk b)
{
    if (a.chk==-1) return b;
    if (b.chk==-1 ) return a;
    tk c;
    c.sum=a.sum+b.sum;
    c.pmn=min(a.pmn,a.sum+b.pmn);
    c.pmx=max(a.pmx,a.sum+b.pmx);
    c.chk=a.chk;
    return c;
}
tk st[4*maxn];
void update(ll id,ll left,ll right,ll x,ll diff)
{
    if (x>right||x<left) return ;
    if (left==right)
    {

        st[id].sum+=diff;
        st[id].pmn=min(0ll,st[id].sum);
        st[id].pmx=max(0ll,st[id].sum);
        st[id].chk=(st[id].sum>=0);
        return ;
    }
    ll mid=(left+right)/2;
    update(id*2,left,mid,x,diff);
    update(id*2+1,mid+1,right,x,diff);
    st[id]=mer(st[id*2],st[id*2+1]);
}
tk get(ll id,ll left,ll right,ll x,ll y)
{
    tk a;
    if (x>right||y<left||x>y) return a;
    if (x<=left&&y>=right) return st[id];
    ll mid=(left+right)/2;
    return mer(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y));
}
vector<int> adj[maxn];
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    ll n=c.size();
    ll q=l.size();
    update(1,1,q+2,1,-base);
    update(1,1,q+2,2,base);
    for (int i=0;i<q;i++)
    {
        adj[l[i]].pb(i+3);
     if(r[i]+1<n)   adj[r[i]+1].pb(-(i+3));
    }

    vector<int> ans;
    for (int i=0;i<n;i++)
    {
        for (auto to:adj[i])
        {
            if (to>0)
            {
                update(1,1,q+2,to,v[to-3]);
            }
            else
            {
                update(1,1,q+2,-to,-v[-to-3]);
            }
        }
        adj[i].clear();
        ll l=1,h=q+2;
        while (l<=h)
        {
            ll mid=(l+h)/2;
            tk p=get(1,1,q+2,mid,q+2);
            if (p.pmx-p.pmn>=c[i]) l=mid+1;
            else h=mid-1;
        }
        tk nw=get(1,1,q+2,h,q+2);
        /*if (i==n-1)
        {
            cout <<h<<" "<<q+2<<endl;
            cout <<nw.sum<<" "<<nw.pmn<<" "<<nw.pmx<<endl;
        }*/
        //assert(nw.pmx-nw.pmn>=c[i]);
       if (h>2) ans.pb((nw.chk ?(int )(c[i]-(nw.pmx-nw.sum)):(int)(nw.sum-nw.pmn)));
       else
       {
           ans.pb(max(0,(int)(nw.sum-base)));
       }
    }
    return ans;
}


/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("test.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    vector<int > l;
    vector<int > r;
    vector<int > v;
    vector<int > t;
    ll n;
     cin>> n;
     while (n--)
     {
         int x;
         cin>> x;
         t.pb(x);
     }
    ll q;
     cin>> q;
     while (q--)
     {
         int a, b, c;
         cin>>a>> b>> c;
         l.pb(a);
         r.pb(b);
         v.pb(c);
     }
     vector<int> ans=distribute_candies(t,l,r,v);
     for (auto to:ans) cout <<to<<endl;


}*/

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