Submission #1246456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246456		Boomyday	Distributing Candies (IOI21_candies)	C++20	0 / 100	554 ms	43592 KiB

candies

//
// Created by adavy on 7/23/2025.
//
#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
using ll = long long;

const int ssz = 262144; // segment tree where the x axis is time

const ll INF = 1e18; // careful!


vector<ll> sg_min(2*ssz, 0), lz_min(2*ssz, 0), sg_max(2*ssz, 0), lz_max(2*ssz, 0);

void push_min(int rt, int tl, int tr){
    sg_min[rt] += lz_min[rt];
    if (tl != tr) {
        lz_min[2*rt] += lz_min[rt];
        lz_min[2*rt+1] += lz_min[rt];
    }
    lz_min[rt] = 0;
}

void push_max(int rt, int tl, int tr){
    sg_max[rt] += lz_max[rt];
    if (tl != tr) {
        lz_max[2*rt] += lz_max[rt];
        lz_max[2*rt+1] += lz_max[rt];
    }
    lz_max[rt] = 0;
}

void upd_min(ll x, int l, int r, int rt, int tl, int tr){
    push_min(rt, tl, tr);
    if (r < tl || l > tr) return;
    if (l <= tl && tr <= r) {
        lz_min[rt] += x;
        push_min(rt, tl, tr);
        return;
    }
    int mid = (tl + tr) / 2;
    upd_min(x, l, r, 2*rt, tl, mid);
    upd_min(x, l, r, 2*rt+1, mid+1, tr);
    sg_min[rt] = min(sg_min[2*rt], sg_min[2*rt+1]);
}

void upd_max(ll x, int l, int r, int rt, int tl, int tr){
    push_max(rt, tl, tr);
    if (r < tl || l > tr) return;
    if (l <= tl && tr <= r) {
        lz_max[rt] += x;
        push_max(rt, tl, tr);
        return;
    }
    int mid = (tl + tr) / 2;
    upd_max(x, l, r, 2*rt, tl, mid);
    upd_max(x, l, r, 2*rt+1, mid+1, tr);
    sg_max[rt] = max(sg_max[2*rt], sg_max[2*rt+1]);
}

ll query_min(int l, int r, int rt, int tl, int tr){
    push_min(rt, tl, tr);
    if (r < tl || l > tr) return INF;
    if (l <= tl && tr <= r) return sg_min[rt];
    int mid = (tl + tr) / 2;
    return min(query_min(l, r, 2*rt, tl, mid), query_min(l, r, 2*rt+1, mid+1, tr));
}

ll query_max(int l, int r, int rt, int tl, int tr){
    push_max(rt, tl, tr);
    if (r < tl || l > tr) return -INF;
    if (l <= tl && tr <= r) return sg_max[rt];
    int mid = (tl + tr) / 2;
    return max(query_max(l, r, 2*rt, tl, mid), query_max(l, r, 2*rt+1, mid+1, tr));
}

int walk_index(ll c, int rt, int tl, int tr, ll&mn, ll&mx){
    push_min(rt, tl, tr);
    push_max(rt, tl, tr);
    if (tl == tr) {
        // we have found the LAST BAD index
        mn = min(sg_min[rt], mn);
        mx = max(sg_max[rt], mx);
        return tl;
    }
    // check if right half is good or bad
    if (max(mx, sg_max[2*rt+1])-min(mn, sg_min[2*rt+1]) >= c){
        // right half is bad, recurse it
        return walk_index(c, 2*rt+1, (tl + tr) / 2 + 1, tr, mn, mx);
    }
    // it's good
    mx = max(mx, sg_max[2*rt+1]);
    mn = min(mn, sg_min[2*rt+1]);
    return walk_index(c, 2*rt, tl, (tl + tr) / 2, mn, mx);
}


std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n, q;
    // adders (time position, value)
    n = c.size();
    q = l.size();

    vector<vector<pair<ll,ll>>> add(n), sub(n); // represents the boxes
    for(int i=0;i<q;++i){
        add[l[i]].push_back({i+2, v[i]});
        sub[r[i]].push_back({i+2, v[i]});
    }
    add[0].push_back({0, ssz}); // deal with bottom edge correctly
    add[1].push_back({1, -ssz});
    vector<int> ans(n, 0);

    for(int i=0;i<n;++i){
        // process additions
        for(auto&[tm,vl]:add[i]){
            upd_max(vl, tm, ssz-1, 1, 0, ssz-1);
            upd_min(vl, tm, ssz-1, 1, 0, ssz-1);
        }


        // process query
        // we need to do a binary search while walking on the segment tree to decide the index where a bad range no longer happens (size less than c[i])
        // find the index of the first non-bad range and the entry before it, determine if that thing is the max or min
        // for the walk, take a range [a, b], and find the values of [m,b]. If it's good, store the min and max values and do on the left subtree,
        // if bad then just recurse this subtree.

        ll mn = INF, mx = -INF;
        int last_bad = walk_index(c[i], 1, 0, ssz-1, mn, mx);
        ll val_bad = query_max(last_bad, last_bad, 1, 0, ssz-1); // value of the last bad range
        ll final = query_max(ssz-1, ssz-1, 1, 0, ssz-1);
        if (val_bad == mn){
            // look at the upper wall
            ll top_mx = query_max(last_bad, ssz-1, 1, 0, ssz-1);
            ans[i] = c[i] - (top_mx-final);
        }
        else {
            // look at the lower wall
            ll bot_mn = query_min(last_bad, ssz-1, 1, 0, ssz-1);
            ans[i] = final - bot_mn;
        }
        // process subtractions
        for (auto&[tm,vl]:sub[i]){
            upd_max(-vl, tm, ssz-1, 1, 0, ssz-1);
            upd_min(-vl, tm, ssz-1, 1, 0, ssz-1);
        }
    }
    return ans;
}

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