Submission #593024

#	Time	Username	Problem	Language	Result	Execution time	Memory
593024		MadokaMagicaFan	Distributing Candies (IOI21_candies)	C++17	0 / 100	106 ms	12452 KiB

candies

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define pry                         cout << "YES\n"
#define prn                         cout << "NO\n"
#define endl                        '\n'

#define fst                         first
#define scn                         second
/* #define ONPC */

using vi = vector<int>;

struct aint{
    int n;
    vi t[2];
    vi lenes;

    aint(vi& v)
        : n(sz(v))
    {
        t[0].assign(4*n,inf);
        t[1].assign(4*n,inf);
        lenes.assign(4*n,0);
    }

    void
    updnd(int i, int l, int r)
    {
        if (l == r) return;
        t[0][i] = min(t[0][i<<1],t[0][i<<1|1]);
        t[1][i] = min(t[1][i<<1],t[1][i<<1|1]);
        return;
    }

    void
    build(int i, int l, int r, vi &v)
    {
        int mid = (l+r)>>1;
        if (l == r) {
            t[0][i] = v[l];
            t[1][i] = 0;
            return;
        }

        build(i<<1, l, mid, v);
        build(i<<1|1, mid+1, r, v);
        updnd(i,l,r);
    }

    void
    update(int i, int l, int r, int tl, int tr)
    {
        int mid = (l+r)>>1;
        if (l > tr || r < tl) return;
        push(i,l,r);
        if (tl <= l && r >= tr) {
        } else {
            update(i<<1, l, mid, tl, tr);
            update(i<<1|1, mid+1, r, tl, tr);

            updnd(i,l,r);
        }

        return;
    }

    void
    push(int i, int l, int r)
    {
        
        return;
    }

    ll
    query(int u)
    {
        return u;
    }
};

int
bs(int x, vi& v)
{
    int l = 0;
    int r = sz(v);
    int mid;

    while (l < r) {
        mid = (l+r)>>1;
        if (v[mid] > x)
            r = mid;
        else
            l = mid+1;
    }
    return l;
}

vi
distribute_candies(vi c, vi l, vi r, vi v)
{
    int n = sz(c);
    int q = sz(l);

    /* aint tr(c); */

    /* Assumes l[j] = 0 ans r[j] = n-1; */
    int bl = 0;
    deque<pair<ll, ll>> vals;

    pair<ll, ll> fn = {inf+5, 0};
    vals.pb(fn);

    for (int j = 0; j < q; ++j) {
        if (!v[j]) continue;
        bl += v[j];
        int x = (v[j] < 0) == 1;
        if (bl < 0) {
            vals.clear();
            vals.pb(fn);
            bl = 0;
        }

        ll delta = v[j];

        while(sz(vals)) {
            if (vals.back().fst <= abs(delta) || (x^(sz(vals)&1)^1)) {
                delta += vals.back().scn;
                vals.pop_back();
            } else break;
        }

        if (x) vals.pb({abs(delta),delta});
        else   vals.pb({delta, delta});
    }

    vi vl;
    vi psum = {0};

    for (int i = sz(vals)-1; i >= 0; --i) {
        vl.pb(vals[i].fst);
        psum.pb(psum.back() + vals[i].scn);
    }

    vi ans;

    for (int i = 0; i < n; ++i) {
        int x = bs(c[i], vl);
        ll a;
        if ((sz(vals)^x)&1) a = 0;
        else                a = c[i];

        a += psum[x];

        a = max(a, 0ll);
        a = min(a, (ll)c[i]);

        ans.pb(a);
    }

    return ans;
}

#ifdef ONPC
void
solve()
{
    int n, q;
    cin >> n >> q;

    vector<int> c(n);
    for (int i = 0; i < n; ++i)
        cin >> c[i];
    
    vector<int> l(q), r(q), v(q);
    for (int i = 0; i < q; ++i)
        cin >> l[i] >> r[i] >> v[i];

    vi ans = distribute_candies(c,l,r,v);

    for (int i = 0; i < sz(ans); ++i) {
        cout << ans[i] << ' ';
    }
    cout << endl;
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

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