Submission #1233560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233560		Timosh	Distributing Candies (IOI21_candies)	C++20	0 / 100	301 ms	34868 KiB

candies

#include "bits/stdc++.h"
#include "candies.h"

using namespace std;
#define ll long long

struct node
{
    ll lz, mx, mn, eq;
};

vector<node> t;
vector<int> C;
vector<ll> ans;
int n;

void push(int l, int r, int i)
{
    if (t[i].eq != -1)
        t[i].lz = t[i].eq, t[i].mn = t[i].mx = t[i].eq;
    else
    {
        if (l != r)
        {
            t[i].mx += t[i].lz;
            t[i].mn += t[i].lz;
        }
        else
            t[i].mx = t[i].mn = t[i].lz;
        if (t[i].mn >= C[0])
            t[i].eq = C[0];
        if (t[i].mx <= 0)
            t[i].eq = 0;
    }
    if (l != r)
    {
        if (t[i].eq != -1)
            t[i * 2].eq = t[i * 2 + 1].eq = t[i].eq;
        else
        {
            t[i * 2].lz += t[i].lz;
            t[i * 2 + 1].lz += t[i].lz;
            t[i].lz = 0;
        }
    }
    if (l == r && t[i].eq != -1)
        t[i].lz = t[i].eq;
    t[i].eq = -1;
}

void upd(int l, int r, int x, int tl = 0, int tr = n - 1, int i = 1)
{
    push(tl, tr, i);
    if (l > tr || tl > r)
        return;
    if (l <= tl && tr <= r && ((x + t[i].mn <= C[0]) == (x + t[i].mx <= C[0]) && (x + t[i].mn < 0) == (x + t[i].mx < 0)))
    {
        if (t[i].mn + x >= C[0])
            t[i].eq = C[0];
        else if (t[i].mx + x <= 0)
            t[i].eq = 0;
        else
            t[i].lz += x;
        push(tl, tr, i);
        return;
    }
    int m = (tl + tr) / 2;
    upd(l, r, x, tl, m, i * 2);
    upd(l, r, x, m + 1, tr, i * 2 + 1);
    t[i].mx = max(t[i * 2].mx, t[i * 2 + 1].mx);
    t[i].mn = min(t[i * 2].mn, t[i * 2 + 1].mn);
}

void get(int tl = 0, int tr = n - 1, int i = 1)
{
    int m = (tl + tr) / 2;
    push(tl, tr, i);
    if (tl == tr)
        ans[tl] = t[i].lz;
    else
    {
        get(tl, m, i * 2);
        get(m + 1, tr, i * 2 + 1);
    }
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    n = c.size();
    C = c;
    t.resize(4 * n);
    for (auto &i : t)
        i.mx = i.mn = i.lz = 0, i.eq = -1;
    ans.resize(n);
    for (int i = 0; i < l.size(); i++)
        upd(l[i], r[i], v[i]);
    get();
    vector<int> ANS(n);
    for (int i = 0; i < n; i++)
        ANS[i] = max(min(ans[i], 1ll * c[i]), 0ll);
    return ANS;
}

// int main()
// {
//     vector<int> x = distribute_candies({5}, {0}, {1}, {3});
//     for (auto &i : x)
//         cout << i << ' ';
//     return 0;
// }

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