제출 #437141

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
437141		ivan100sic	사탕 분배 (IOI21_candies)	C++17	100 / 100	446 ms	36472 KiB

candies

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

using vi = vector<int>;
using ll = long long;

struct node {
    ll l, h, s;

    node(ll v = 0) : l(min(0ll, v)), h(max(0ll, v)), s(v) {}

    node(ll l, ll h, ll s) : l(l), h(h), s(s) {}

    node operator+ (const node& b) const {
        return { min(l, s + b.l), max(h, s + b.h), s + b.s };
    }
};

struct state {
    ll l, r, q;

    operator bool() const {
        return l <= r;
    }

    ll operator() (ll x) const {
        if (x < q) {
            return l;
        } else {
            return min(x - q + l, r);
        }
    }

    state(node n, ll c) {
        l = n.s - n.l;
        r = c + n.s - n.h;
        q = min(c, -n.l);
    }
};

struct segtree {
    static constexpr int maxn = 262144;

    vector<node> a;

    segtree() : a(2*maxn) {}

    void update(int p, int v) {
        p += maxn;
        a[p] = node(v);
        for (int x=p>>1; x; x>>=1) {
            a[x] = a[2*x] + a[2*x+1];
        }
    }

    ll solve(ll y, ll c, int x=1, int w=maxn) {
        if (w == 1) {
            return min(c, max(0ll, y + a[x].s));
        }
        auto st = state(a[x], c);
        if (st) {
            return st(y);
        }

        auto st_r = state(a[2*x+1], c);
        
        if (st_r) {
            return st_r(solve(y, c, 2*x, w >> 1));
        } else {
            return solve(0, c, 2*x+1, w >> 1);
        }
    }
};

vi distribute_candies(vi c, vi l, vi r, vi v) {
    int n = c.size();
    int q = l.size();
    vector<vi> e(n+1), f(n+1);
    for (int i=0; i<q; i++) {
        e[l[i]].push_back(i);
        f[r[i]+1].push_back(i);
    }
    segtree st;
    vi sol(n);
    for (int i=0; i<n; i++) {
        for (int j : e[i]) {
            st.update(j, v[j]);
        }

        for (int j : f[i]) {
            st.update(j, 0);
        }
        
        sol[i] = st.solve(0, c[i]);
    }
    return sol;
}

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