Submission #1243591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243591		raphaelp	Distributing Candies (IOI21_candies)	C++20	0 / 100	331 ms	45780 KiB

candies

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

#define int long long
class SegTree
{
private:
    int N;
    vector<int> minn, maxx, swapped, sum;
    int l(int x) { return (x << 1); }
    int r(int x) { return (x << 1) + 1; }
    void update(int L, int R, int a, int val, int x)
    {
        if (L > a || R < a)
            return;
        if (L == a && R == a)
        {
            maxx[x] = max(0LL, val), minn[x] = min(0LL, val), sum[x] = val;
        }
        else
        {
            int m = (L + R) / 2;
            update(L, m, a, val, l(x));
            update(m + 1, R, a, val, r(x));
            sum[x] = sum[l(x)] + sum[r(x)];
            minn[x] = minn[l(x)];
            swapped[x] = 0;
            if (minn[r(x)] + sum[l(x)] < minn[x])
            {
                minn[x] = minn[r(x)] + sum[l(x)];
                swapped[x] = 1;
            }
            maxx[x] = maxx[l(x)];
            if (maxx[r(x)] + sum[x] > maxx[x])
            {
                maxx[x] = maxx[r(x)] + sum[x];
                if (swapped[x])
                    swapped[x] = swapped[r(x)];
            }
            else if (swapped[x] == 0)
                swapped[x] = swapped[l(x)];
        }
    }
    int Q(int L, int R, int range, int x)
    {
        if (maxx[x] - minn[x] <= range)
            return sum[x];
        if (L == R || (maxx[r(x)] - minn[r(x)] <= range && (maxx[r(x)] + sum[l(x)] - minn[l(x)] > range || maxx[l(x)] - sum[l(x)] - minn[r(x)] > range)))
        {
            int ans = maxx[x];
            if (swapped[x])
                ans = minn[x];
            ans = sum[x] - ans;
            if (ans < 0)
                ans += range;
            return ans;
        }
        int m = (L + R) / 2;
        if (maxx[r(x)] - minn[r(x)] > range)
            return Q(m + 1, R, range, r(x));
        return Q(L, m, range, l(x)) + sum[r(x)];
    }

public:
    SegTree(int n)
    {
        N = pow(2, ceil(log2(n)));
        minn.assign(2 * N, 0);
        maxx.assign(2 * N, 0);
        swapped.assign(2 * N, 0);
        sum.assign(2 * N, 0);
    }
    void update(int x, int val) { update(0, N - 1, x, val, 1); }
    int Q(int range) { return Q(0, N - 1, range, 1); }
};

vector<signed> distribute_candies(vector<signed> C, vector<signed> L, vector<signed> R, vector<signed> V)
{
    int N = C.size(), Q = L.size();
    vector<signed> ans(N);
    SegTree ST(Q);
    vector<vector<int>> Tab;
    for (int i = 0; i < Q; i++)
    {
        Tab.push_back({L[i], i, V[i]});
        Tab.push_back({R[i] + 1, i, 0});
    }
    sort(Tab.begin(), Tab.end());
    int buff = 0;
    for (int i = 0; i < N; i++)
    {
        while (Tab[buff][0] == i)
        {
            ST.update(Tab[buff][1], Tab[buff][2]);
            buff++;
        }
        ans[i] = ST.Q(C[i]);
    }
    return ans;
}

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