Submission #1243651

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

candies

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

class SegTree
{
private:
    long long N;
    vector<long long> minn, maxx, swapped, sum;
    long long l(long long x) { return (x << 1); }
    long long r(long long x) { return (x << 1) + 1; }
    void update(long long L, long long R, long long a, long long val, long long 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
        {
            long long 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)];
        }
    }
    long long Q(long long L, long long R, long long range, long long x)
    {
        if (maxx[x] - minn[x] <= range)
            return sum[x] - minn[x];
        if (L == R || (maxx[r(x)] - minn[r(x)] < range && minn[r(x)] + sum[l(x)] < minn[l(x)]))
        {
            if (swapped[x])
            {
                return max(range, (sum[x] - minn[x]));
            }
            else
                return max(0LL, range + sum[x] - maxx[x]);
        }
        long long 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(long long 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(long long x, long long val) { update(0, N - 1, x, val, 1); }
    long long Q(long long range) { return Q(0, N - 1, range, 1); }
};

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V)
{
    long long N = C.size(), Q = L.size();
    vector<int> ans(N);
    SegTree ST(Q);
    vector<vector<long long>> Tab;
    for (long long 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());
    long long buff = 0;
    for (long long i = 0; i < N; i++)
    {
        while (buff < Tab.size() && Tab[buff][0] == i)
        {
            ST.update(Tab[buff][1], Tab[buff][2]);
            buff++;
        }
        ans[i] = ST.Q(C[i]);
    }
    return ans;
}
/*int main()
{
    int N, Q;
    cin >> N >> Q;
    vector<int> C(N), L(Q), R(Q), V(Q);
    for (int i = 0; i < N; i++)
        cin >> C[i];
    for (int i = 0; i < Q; i++)
        cin >> L[i] >> R[i] >> V[i];
    vector<int> ans = distribute_candies(C, L, R, V);
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << ' ';
}*/

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