Submission #815940

#	Time	Username	Problem	Language	Result	Execution time	Memory
815940		PixelCat	Distributing Candies (IOI21_candies)	C++17	100 / 100	235 ms	37968 KiB

candies

#include "candies.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

inline void chmin(int &x, const int &v) {
    x = min(x, v);
}
inline void chmax(int &x, const int &v) {
    x = max(x, v);
}

const int MAXN = 1 << 18;
const int MAXQ = MAXN;
const int INF = 1e18;

// single point add, min/max sum query on suffixs
#define L(id) ((id) * 2)
#define R(id) ((id) * 2 + 1)
struct SegTree {
    struct Node {
        int mns, mxs, sum;
        // min suffix, max suffix, sum
    } a[MAXN << 1];

    inline void pull(int id) {
        a[id].mns = min(a[L(id)].mns + a[R(id)].sum, a[R(id)].mns);
        a[id].mxs = max(a[L(id)].mxs + a[R(id)].sum, a[R(id)].mxs);
        a[id].sum = a[L(id)].sum + a[R(id)].sum;
    }

    // initialize
    void build() {
        memset(a, 0, sizeof(a));
    }

    // add value for a single point
    void single_add(int pos, int val) {
        int id = pos + MAXN;
        a[id].mns += val;
        a[id].mxs += val;
        a[id].sum += val;
        for(id /= 2; id; id /= 2) pull(id);
    }

    // {pos, {min, max}}
    int solve(int c) {
        int id = 1, l = 0, r = MAXN - 1;
        int mx = 0, mn = 0, sum = 0;
        while(l != r) {
            int nmx = max(mx, a[R(id)].mxs + sum);
            int nmn = min(mn, a[R(id)].mns + sum);
            int m = l + (r - l) / 2;
            if(nmx - nmn > c) {
                id = R(id);
                l = m + 1;
            } else {
                mx = nmx; mn = nmn;
                sum += a[R(id)].sum;
                id = L(id);
                r = m;
            }
        }
        if(a[id].sum < 0) return c - mx;
        else              return -mn;
    }
} seg;

vector<i32> distribute_candies(vector<i32> C, vector<i32> LE, vector<i32> RI, vector<i32> VAL) {
    int n = sz(C);
    int q = sz(VAL);

    seg.build();
    seg.single_add(0, INF);

    struct Event { int time, pos, val; };
    vector<Event> ev;
    For(i, 0, q - 1) {
        ev.push_back({LE[i], i + 1, -VAL[i]});
        ev.push_back({RI[i] + 1, i + 1, VAL[i]});
    }
    sort(all(ev), [&](const Event &e1, const Event &e2) {
        return e1.time > e2.time;
    });

    vector<int> ans(n);
    For(i, 0, n - 1) {
        while(sz(ev) && ev.back().time == i) {
            auto e = ev.back(); ev.pop_back();
            seg.single_add(e.pos, e.val);
        }
        int c = C[i];
        ans[i] = seg.solve(c);
    }
    return vector<i32>(all(ans));
}

/*

3
10 15 13
2
0 2 20
0 1 -11

0 4 13

*/

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