Submission #623255

#	Time	Username	Problem	Language	Result	Execution time	Memory
623255		cheissmart	Distributing Candies (IOI21_candies)	C++17	100 / 100	1507 ms	45388 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 7;
const ll oo = 1e18;

int c[N], n, q;
V<pi> ev[N];

namespace brute {
    ll a[N];
    void add(int l, int r, int x) {
        assert(0 <= l && l < r && r <= q + 1);
        for(int i = l; i < r; i++) {
            a[i] += x;
        }
    }
    ll qmax(int l, int r) {
        assert(0 <= l && l < r && r <= q + 1);
        ll mx = -oo;
        for(int i = l; i < r; i++) {
            mx = max(mx, a[i]);
        }
        return mx;
    }
    ll qmin(int l, int r) {
        assert(0 <= l && l < r && r <= q + 1);
        ll mn = oo;
        for(int i = l; i < r; i++) {
            mn = min(mn, a[i]);
        }
        return mn;
    }
}

namespace DS {

struct node {
    ll mn, mx, lz;
    node() {
        mn = mx = lz = 0;
    }
} t[N * 4];

void apply(int v, ll x) {
    t[v].lz += x;
    t[v].mn += x;
    t[v].mx += x;
}
void push(int v) {
    apply(v * 2, t[v].lz);
    apply(v * 2 + 1, t[v].lz);
    t[v].lz = 0;
}
void pull(int v) {
    t[v].mn = min(t[v * 2].mn, t[v * 2 + 1].mn);
    t[v].mx = max(t[v * 2].mx, t[v * 2 + 1].mx);
}

void add(int l, int r, ll x, int v = 1, int tl = 0, int tr = q + 1) {
    if(l <= tl && tr <= r) {
        apply(v, x);
        return;
    }
    push(v);
    int tm = (tl + tr) / 2;
    if(l < tm) add(l, r, x, v * 2, tl, tm);
    if(r > tm) add(l, r, x, v * 2 + 1, tm, tr);
    pull(v);
}

ll qmin(int l, int r, int v = 1, int tl = 0, int tr = q + 1){
    if(l <= tl && tr <= r)
        return t[v].mn;
    push(v);
    int tm = (tl + tr) / 2;
    ll res = oo;
    if(l < tm) res = min(res, qmin(l, r, v * 2, tl, tm));
    if(r > tm) res = min(res, qmin(l, r, v * 2 + 1, tm, tr));
    return res;
}

ll qmax(int l, int r, int v = 1, int tl = 0, int tr = q + 1){
    if(l <= tl && tr <= r)
        return t[v].mx;
    push(v);
    int tm = (tl + tr) / 2;
    ll res = -oo;
    if(l < tm) res = max(res, qmax(l, r, v * 2, tl, tm));
    if(r > tm) res = max(res, qmax(l, r, v * 2 + 1, tm, tr));
    return res;
}

}

using namespace DS;

vi distribute_candies(vi _c, vi _l, vi _r, vi _v) {
    n = SZ(_c), q = SZ(_l);
    for(int i = 0; i < n; i++)
        c[i] = _c[i];

    vi ans(n);

    for(int i = 1; i <= q; i++) {
        int l = _l[i - 1], r = _r[i - 1], v = _v[i - 1];
        ev[l].EB(i, v);
        ev[r + 1].EB(i, -v);
    }

    for(int i = 0; i < n; i++) {
        for(auto [pos, val]:ev[i]) {
            add(pos, q + 1, val);
        }
        ll final = qmax(q, q + 1);
        ll mx = qmax(0, q + 1);
        ll mn = qmin(0, q + 1);
        if(mx - mn <= c[i]) {
            ans[i] = final - mn;
        } else {
            int lb = 0, rb = q;
            while(lb <= rb) {
                int mb = (lb + rb) / 2;
                ll mx = qmax(mb, q + 1);
                ll mn = qmin(mb, q + 1);
                if(mx - mn <= c[i])
                    rb = mb - 1;
                else
                    lb = mb + 1;
            }
            ll mx = qmax(rb, q + 1);
            ll mn = qmin(rb, q + 1);
            assert(mx - mn > c[i]);
            ll val = qmax(rb, rb + 1);
            if(val == mx) {
                ans[i] = final - mn;
            } else {
                ans[i] = final - (mx - c[i]);
            }
        }
    }

    return ans;
}

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