Submission #814387

#	Time	Username	Problem	Language	Result	Execution time	Memory
814387		alvingogo	Distributing Candies (IOI21_candies)	C++17	0 / 100	267 ms	34084 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

int c;
struct ST{
    struct no{
        int l,r,k;
        no(int a,int b,int c){
            l=a;
            r=b;
            k=c;
        }
        int get(int x){
            if(x<=l){
                return k;
            }
            return k+(min(x,r))-l;
        }
    };
    vector<no> st;
    void init(int x){
        st.resize(4*x,{0,c,0});
    }
    void pull(int v){
        no& a=st[2*v+1];
        no& b=st[2*v+2];
        no& c=st[v];
        int d=b.get(a.k),e=b.get(a.k+a.r-a.l);
        c.k=d;
        if(e==d){
            c.l=a.l;
        }
        else{
            c.l=a.l+max(0,(b.l-a.k));
        }
        c.r=c.l+(e-d);
    }
    void update(int v,int L,int R,int p,int x){
        if(L==R){
            if(x==0){
                st[v].l=0;
                st[v].r=c;
                st[v].k=0;
            }
            else if(x<0){
                st[v].l-=x;
            }
            else{
                st[v].r-=x;
                st[v].k+=x;
            }
            return;
        }
        int m=(L+R)/2;
        if(p<=m){
            update(2*v+1,L,m,p,x);
        }
        else{
            update(2*v+2,m+1,R,p,x);
        }
        pull(v);
    }
    int query(int x){
        return st[0].get(x);
    }
}st;
vector<int> distribute_candies(vector<int> w, vector<int> l,
                                    vector<int> r, vector<int> v) {
    int n=w.size();
    c=w[0];
    vector<int> ans(n);
    int q=l.size();
    st.init(q);
    vector<vector<pair<int,int> > > upd(n),del(n);
    for(int i=0;i<q;i++){
        if(abs(v[i])>c){
            if(v[i]<0){
                v[i]=-c;
            }
            else{
                v[i]=c;
            }
        }
        upd[l[i]].push_back({i,v[i]});
        del[r[i]].push_back({i,v[i]});
    }
    for(int i=0;i<n;i++){
        for(auto h:upd[i]){
            st.update(0,0,n-1,h.fs,h.sc);
        }
        ans[i]=st.query(0);
        for(auto h:del[i]){
            st.update(0,0,n-1,h.fs,0);
        }
    }
    return ans;
}

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