Submission #1075764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075764		PoPularPlusPlus	Distributing Candies (IOI21_candies)	C++17	29 / 100	568 ms	27588 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define vf first
#define vs second

vector<int> cap;

struct Seg {
    vector<ll> lazy , set_val , val;
    int siz;

    void init(int n){
        siz = 1;
        while(siz < n)siz *= 2;
        lazy.assign(siz * 2 , 0);
        set_val.assign(siz * 2 , -1);
        val.assign(siz * 2 , 0);

    }

    void push(int x){
        if(set_val[x] != -1){
            set_val[2*x+1] = set_val[x];
            set_val[2*x+2] = set_val[x];
            lazy[2*x+1] = lazy[2*x+2] = lazy[x];
            lazy[x] = 0;
            set_val[x] = -1;
        }
        else {
            lazy[2*x+1] += lazy[x];
            lazy[2*x+2] += lazy[x];
            lazy[x] = 0;
        }
    }

    ll get(int pos , int x , int lx , int rx){
        if(rx - lx == 1){
            if(set_val[x] != -1){
                if(set_val[x] == 0)val[x] = lazy[x];
                else val[x] = cap[lx] + lazy[x];
            }
            else val[x] += lazy[x];
            val[x] = max(val[x] , 0LL);
            val[x] = min(val[x] , 0LL + cap[lx]);
            set_val[x] = -1;
            lazy[x] = 0;
            return val[x];
        }
        push(x);
        int m = (lx + rx)/2;
        if(pos < m)return get(pos , 2 * x + 1 , lx , m);
        else return get(pos , 2 * x + 2 , m, rx);
    }

    ll get(int pos){
        return get(pos, 0 , 0 , siz);
    }

    void set(int l ,int r, ll value , int x , int lx , int rx){
        if(lx >= r || l >= rx)return;
        if(lx >= l && rx <= r){
            set_val[x] = value;
            lazy[x] = 0;
            return;
        }

        push(x);
        int m = (lx + rx)/2;
        set(l , r , value , 2 * x + 1 , lx , m);
        set(l ,r , value , 2 * x + 2 , m, rx);
    }

    void set(int l , int r , ll value){
        set(l , r , value , 0 , 0, siz);
    }

    void add(int l ,int r , ll value , int x , int lx , int rx){
        if(lx >= r || l >= rx)return;
        if(lx >= l && rx <= r){
            lazy[x] += value;
            return;
        }
        push(x);

        int m = (lx + rx)/2;
        add(l ,r , value , 2 * x + 1 , lx , m);
        add(l , r , value , 2 * x + 2 , m , rx);
    }

    void add(int l , int r , ll value){
        add(l , r , value , 0 ,0 ,siz);
    }
};

Seg st;
int n;

void query(ll val){
    int l = 0 , r = n-1;
    int pos = -1;
    while(l <= r){
        int mid = (l + r)/2;
        ll x = st.get(mid);
        x = max(x , 0LL);
        if(x >= cap[mid])x = cap[mid];
        x += val;
        if(x <= 0 || x >= cap[mid]){
            pos = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }

    //cout << "pos " << pos << endl;

    if(pos < n-1){
        st.add(pos+1 , n , val);
    }

    if(pos >= 0){
        if(val < 0){
            st.set(0 , pos + 1 , 0);
        }
        else st.set(0 , pos + 1 , 1e9);
    }
}

vector<int> distribute_candies(vector<int> c, vector<int> l,vector<int> r, vector<int> v){
    n = c.size();
    cap = c;
    vector<int> res(n);
    st.init(n + 1);
    int q = l.size();
    vector<pair<int,int>> tp;
    for(int i = 0; i < n; i++){
        tp.pb(mp(c[i] , i));
    }
    sort(all(cap));
    sort(all(tp));
    for(int i = 0; i < q; i++){
        query(v[i]);
    }

    for(int i = 0; i < n; i++)res[tp[i].vs] = st.get(i);

    return res;
}

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