Submission #595420

#	Time	Username	Problem	Language	Result	Execution time	Memory
595420		PiejanVDC	Distributing Candies (IOI21_candies)	C++17	100 / 100	1767 ms	99312 KiB

candies

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

struct UPDATE {
    long long l,r,v,p;
};

int l,r;
long long val;

vector<long long>mn, mx, mn_lazy, mx_lazy, st;

long long sum_query(int i, int j, int p) {
    if(i > r || j < l)
        return 0;
    if(i >= l && j <= r)
        return st[p];
    int mid = (i+j)/2;
    return sum_query(i, mid, 2*p) + sum_query(mid+1, j, 2*p+1);
}

void sum_update(int i, int j, int p) {
    if(i > r || j < l)
        return;
    if(i == j) {
        st[p] += val;
        return;
    }
    int mid = (i+j)/2;
    sum_update(i, mid, 2*p);
    sum_update(mid+1, j, 2*p+1);
    st[p] = st[2*p] + st[2*p+1];
}

long long min_query(int i, int j, int p) {
    if(i >= l && j <= r)
        return mn[p] + mn_lazy[p];
    
    mn_lazy[2*p] += mn_lazy[p];
    mn_lazy[2*p+1] += mn_lazy[p];
    mn[p] += mn_lazy[p];
    mn_lazy[p] = 0;

    int mid = (i+j)/2;
    
    long long ret = LLONG_MAX;
    if(l <= mid)
        ret = min_query(i, mid, 2*p);
    if(r > mid)
        ret = min(ret, min_query(mid+1, j, 2*p+1));

    return ret;
}

long long max_query(int i, int j, int p) {
    if(i >= l && j <= r)
        return mx[p] + mx_lazy[p];
    
    //cout << i << ' ' << j << '\n';

    mx_lazy[2*p] += mx_lazy[p];
    mx_lazy[2*p+1] += mx_lazy[p];
    mx[p] += mx_lazy[p];
    mx_lazy[p] = 0;

    int mid = (i+j)/2;
    
    long long ret = LLONG_MIN;
    if(l <= mid)
        ret = max_query(i, mid, 2*p);
    if(r > mid)
        ret = max(ret, max_query(mid+1, j, 2*p+1));

    return ret;
}

pair<long long, long long> update(int i, int j, int p) {
    if(i > r || j < l)
        return {mn[p] + mn_lazy[p], mx[p] + mx_lazy[p]};

    if(i >= l && j <= r) {
        mn_lazy[p] += val;
        mx_lazy[p] += val;
        return {mn[p] + mn_lazy[p], mx[p] + mx_lazy[p]};
    }

    mn_lazy[2*p] += mn_lazy[p];
    mn_lazy[2*p+1] += mn_lazy[p];
    mn_lazy[p] = 0;
    mx_lazy[2*p] += mx_lazy[p];
    mx_lazy[2*p+1] += mx_lazy[p];
    mx_lazy[p] = 0;

    int mid = (i+j)/2;

    pair<long long, long long> ret = {LLONG_MAX, LLONG_MIN};

    ret = update(i, mid, 2*p);
    auto z = update(mid+1, j, 2*p+1);
    ret.first = min(ret.first, z.first);
    ret.second = max(ret.second, z.second);

    mn[p] = ret.first, mx[p] = ret.second;
    return ret;
}

vector<int>distribute_candies(vector<int>c, vector<int>L, vector<int>R, vector<int>V) {
 
    const int n = (int)c.size();
    const int m = (int)L.size();
 
    long long value = 0;

    mn.resize(8*m, 0);
    mx.resize(8*m, 0);
    mn_lazy.resize(8*m, 0);
    mx_lazy.resize(8*m, 0);
    st.resize(8*m, 0);

    vector<int>ans(n);
 
    vector<vector<UPDATE>>upd(n+1);

    for(int i = 0 ; i < m ; i++) {
        UPDATE Upd;
        Upd.l = L[i], Upd.r = R[i], Upd.v = V[i]; Upd.p = i;
        upd[L[i]].push_back(Upd);
        upd[R[i]+1].push_back(Upd);
    }

    //   

    for(int i = 0 ; i < n ; i++) {
        for(auto z : upd[i]) {
            if(z.l == i) {
                val = z.v;
                l = z.p, r = m-1;
                value += z.v;
                update(0, m-1, 1);

                l = 0;
                //if(!i)cout << min_query(0, m-1, 1) << '-';

                l = r = z.p;
                val = z.v;
                sum_update(0, m-1, 1);
            } else {
                val = -z.v;
                l = z.p, r = m-1;
                value -= z.v;
                update(0, m-1, 1);

                l = r = z.p;
                val = -z.v;
                sum_update(0, m-1, 1);
            }
        }

        int p = m+1;
        int le = 0, re = m-1;
 
        while(le <= re) {
            int mid = (le+re)/2;
            l = mid, r = m-1;
            long long suff_max = max_query(0, m-1, 1);
            long long suff_min = min_query(0, m-1, 1);
            
            //cout << mid << ' ' << suff_max << ' ' << suff_min << '\n';

            if(suff_max - suff_min > c[i]) {
                le = mid+1, p = mid;
            } else {
                re = mid-1;
            }
        }

        if(p == m+1) {
            l = 0, r = m-1;
            //cout << max_query(0, m-1, 1) << ' ';
            if(max_query(0, m-1, 1) > c[i]) {
                ans[i] = max(c[i] - (max_query(0, m-1, 1) - value), 0LL);
                continue;
            }
            l = 0;
            ans[i] = value - min(0LL,min_query(0, m-1, 1));
            continue;
        }
 
        // 0 0 0
        // 10 15 13
        // 0 4 13

        // 20 20 20
        // 9 9 9 

        l = 0, r = p;
        long long value_p = sum_query(0, m-1, 1);

        l = p, r = m-1;

        //cout << i << ' ' << value << ' ' << value_p << ' ' << min_query(0, m-1, 1) << ' ' << max_query(0, m-1, 1) << '\n';
        if(value_p == min_query(0, m-1, 1)) { // smaller side 
            ans[i] = max(c[i] - (max_query(0, m-1, 1) - value), 0LL);
        } else {
            ans[i] = max(value - min_query(0, m-1, 1), 0LL);
        }
 
    }
 
    return ans;
}

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