제출 #435228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
435228		Lam_lai_cuoc_doi	사탕 분배 (IOI21_candies)	C++17	40 / 100	555 ms	13960 KiB

candies

#include "candies.h"

#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;
using ll = long long;

constexpr int N = 2e5 + 2;
constexpr int block = 450;

struct BLOCKSQRT
{
    int n, t[block], in[N];
    ll c[N], lazy[N], st[block];
    int piv, beg[block], en[block];

    BLOCKSQRT()
    {
        memset(t, -1, sizeof t);
    }

    void Build()
    {
        for (int i = 1; i <= n; ++i)
        {
            in[i] = i / block;

            if (!beg[in[i]])
                beg[in[i]] = i;
            en[in[i]] = i;
        }
    }

    ll Get(int x)
    {
        return (t[in[x]] ? (t[in[x]] == -1 ? 0 : c[x]) : lazy[x]) + st[in[x]];
    }

    void Update(int l, int r, int v)
    {
        if (l > r)
            return;

        if (t[in[l]])
        {
            for (int i = beg[in[l]]; i <= en[in[l]]; ++i)
                lazy[i] = t[in[l]] == -1 ? 0 : c[i];
            t[in[l]] = 0;
        }

        for (int i = l; i <= en[in[l]] && i <= r; ++i)
            lazy[i] += v;

        if (in[l] != in[r])
        {
            for (int i = in[l] + 1; i < in[r]; ++i)
                st[i] += v;

            if (t[in[r]])
            {
                for (int i = beg[in[r]]; i <= en[in[r]]; ++i)
                    lazy[i] = t[in[r]] == -1 ? 0 : c[i];
                t[in[r]] = 0;
            }

            for (int i = beg[in[r]]; i <= r; ++i)
                lazy[i] += v;
        }
    }

    void Assign(int l, int r, int v)
    {
        if (l > r)
            return;

        for (int i = beg[in[l]]; i <= en[in[l]]; ++i)
            lazy[i] = (t[in[l]] ? (t[in[l]] == -1 ? 0 : c[i]) : lazy[i]) + st[in[l]];
        t[in[l]] = st[in[l]] = 0;

        for (int i = l; i <= en[in[l]] && i <= r; ++i)
            lazy[i] = (v == 1 ? c[i] : 0);

        if (in[l] != in[r])
        {
            for (int i = in[l] + 1; i < in[r]; ++i)
            {
                t[i] = v;
                st[i] = 0;
            }

            for (int i = beg[in[r]]; i <= en[in[r]]; ++i)
                lazy[i] = (t[in[r]] ? (t[in[r]] == -1 ? 0 : c[i]) : lazy[i]) + st[in[r]];
            st[in[r]] = t[in[r]] = 0;

            for (int i = beg[in[r]]; i <= r; ++i)
                lazy[i] = (v == 1 ? c[i] : 0);
        }
    }

    void SetFull(int l, int r)
    {
        Assign(l, r, 1);
    }

    void SetEmpty(int l, int r)
    {
        Assign(l, r, -1);
    }
} f;

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    int n = c.size(), q = r.size();
    vector<int> ans(n, 0), id(n, 0), rev(n, 0);
    vector<ll> tmp(n, 0);

    /*Sub1*/

    if (1ll * n * q <= 2e7)
    {
        for (int i = 0; i < q; ++i)
        {
            for (int j = l[i]; j <= r[i]; ++j)
                ans[j] = max(0, min(c[j], ans[j] + v[i]));
        }

        return ans;
    }

    /*Sub2*/
    {
        for (auto i : v)
            if (i < 0)
                goto noSub2;

        for (int i = 0; i < q; ++i)
        {
            tmp[l[i]] += v[i];
            if (r[i] < n - 1)
                tmp[r[i] + 1] -= v[i];
        }

        for (int i = 0; i < n; ++i)
        {
            if (i)
                tmp[i] += tmp[i - 1];

            ans[i] = min((ll)c[i], tmp[i]);
        }

        return ans;
    }

noSub2:;

    /*Sub4*/

    {
        for (auto i : l)
            if (i != 0)
                goto noSub4;

        for (auto i : r)
            if (i != n - 1)
                goto noSub4;

        for (int i = 0; i < n; ++i)
            id[i] = i;

        sort(id.begin(), id.end(), [&](const int &x, const int &y)
             { return c[x] < c[y]; });

        f.n = f.piv = n;
        for (int i = 0; i < n; ++i)
            f.c[rev[id[i]] = i + 1] = c[id[i]];

        f.Build();

        for (int i = 0; i < q; ++i)
            if (v[i] < 0)
            {
                int left = 1, mid, right = n;
                while (left <= right)
                {
                    mid = (left + right) / 2;
                    if (f.Get(mid) <= -v[i])
                        left = mid + 1;
                    else
                        right = mid - 1;
                }
                f.SetEmpty(1, right);
                f.Update(left, n, v[i]);
            }
            else if (v[i] > 0)
            {
                int left = 1, mid, right = n;
                while (left <= right)
                {
                    mid = (left + right) / 2;
                    if (f.c[mid] - f.Get(mid) <= v[i])
                        left = mid + 1;
                    else
                        right = mid - 1;
                }

                f.SetFull(1, right);
                f.Update(left, n, v[i]);
            }

        for (int i = 0; i < n; ++i)
            ans[i] = f.Get(rev[i]);

        return ans;
    }

noSub4:;
    return ans;
}

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