Submission #831922

#	Time	Username	Problem	Language	Result	Execution time	Memory
831922		Johann	사탕 분배 (IOI21_candies)	C++17	27 / 100	305 ms	32800 KiB

candies

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

typedef long long ll;
typedef vector<ll> vi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N, Q;
vi C, L, R, V;
vector<int> ans;

struct operation
{
    int op;     // -1 or 1: inner min or inner max
    ll a, b, d; // -1: max(min(x + a, b), d) or 1: min(max(x + a, b), d)
    void swap()
    {
        ll oldD = d;
        if (op == -1)
            d = max(oldD, b);
        else
            d = min(oldD, b);
        op *= -1;
        b = oldD;
    }
    ll eval(ll x)
    {
        if (op == 1)
            swap();
        return max(min(x + a, b), d);
    }
};
struct segtree
{
    int size;
    vector<operation> arr;
    ll c;
    void init(int _size, int _c)
    {
        c = _c;
        size = 1;
        while (size < _size)
            size *= 2;
        arr.assign(2 * size, {1, 0, 0, c});
    }
    operation apply(operation a, operation b)
    {
        // b(a(x))
        if (a.op != -1)
            a.swap();
        if (b.op != 1)
            b.swap();
        ll tmp = max(a.d + b.a, b.b);
        operation ret;
        ret.op = 1;
        ret.a = a.a + b.a;
        ret.b = tmp;
        ret.d = min(max(tmp, a.b + b.a), b.d);
        return ret;
    }
    void propagate(int x)
    {
        assert(x < size);
        arr[2 * x] = apply(arr[2 * x], arr[x]);
        arr[2 * x + 1] = apply(arr[2 * x + 1], arr[x]);
        arr[x] = {-1, 0, c, 0};
    }
    void update(int l, int r, ll v)
    {
        if (v > 0)
            update(l, r, {-1, v, c, 0}, 1, 0, size);
        else
            update(l, r, {1, v, 0, c}, 1, 0, size);
    }
    void update(int l, int r, operation op, int x, int lx, int rx)
    {
        if (l <= lx && rx <= r)
        {
            arr[x] = apply(arr[x], op);
            return;
        }
        if (r <= lx || rx <= l)
            return;
        int m = (lx + rx) / 2;
        propagate(x);
        update(l, r, op, 2 * x, lx, m);
        update(l, r, op, 2 * x + 1, m, rx);
    }
    void queryAns() { queryAns(1, 0, size); }
    void queryAns(int x, int lx, int rx)
    {
        if (x >= size)
        {
            if (lx < sz(ans))
                ans[lx] = arr[x].eval(0);
            return;
        }
        propagate(x);
        int m = (lx + rx) / 2;
        queryAns(2 * x, lx, m);
        queryAns(2 * x + 1, m, rx);
    }
};
segtree seg;

std::vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    C = vi(all(c));
    N = sz(c);
    Q = sz(l);

    seg.init(N, C[0]);

    for (int q = 0; q < Q; ++q)
        seg.update(l[q], ++r[q], v[q]);

    ans.resize(N);
    seg.queryAns();

    return ans;
}

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