Submission #813796

#	Time	Username	Problem	Language	Result	Execution time	Memory
813796		PixelCat	Distributing Candies (IOI21_candies)	C++17	29 / 100	530 ms	34112 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 = 200'000;
const int MAXQ = MAXN;
const int INF = 1e18;

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

    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 id, int l, int r, int pos, int val) {
        if(l == r) {
            a[id].mns += val;
            a[id].mxs += val;
            a[id].sum += val;
            return;
        }
        int m = l + (r - l) / 2;
        if(pos <= m) single_add(L(id), l, m, pos, val);
        if(pos > m)  single_add(R(id), m + 1, r, pos, val);
        pull(id);
    }

    // search for maximum suffix sum for all [i > pos]
    // return: {max suf, suf sum}
    pii max_suf(int id, int l, int r, int pos) {
        if(pos > r) return pii(-INF, 0);
        if(pos <= l) return pii(a[id].mxs, a[id].sum);
        int m = l + (r - l) / 2;
        pii pl = max_suf(L(id), l, m, pos);
        pii pr = max_suf(R(id), m + 1, r, pos);
        return pii(max(pl.F + pr.S, pr.F), pl.S + pr.S);
    }

    // search for minimum suffix sum for all [i > pos]
    // return: {min suf, suf sum}
    pii min_suf(int id, int l, int r, int pos) {
        if(pos > r) return pii(INF, 0);
        if(pos <= l) return pii(a[id].mns, a[id].sum);
        int m = l + (r - l) / 2;
        pii pl = min_suf(L(id), l, m, pos);
        pii pr = min_suf(R(id), m + 1, r, pos);
        return pii(min(pl.F + pr.S, pr.F), pl.S + pr.S);
    }
} seg;

// search for last (rightmost) position where [dif > c]
int search(int q, int c) {
    int lo = 0, hi = q + 1;
    while(hi - lo > 1) {
        int mi = (hi + lo) / 2;
        int dif = seg.max_suf(0, 0, q + 1, mi).F - seg.min_suf(0, 0, q + 1, mi).F;
        if(dif > c) lo = mi;
        else hi = mi;
    }
    return lo;
}

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

    vector<int> a(q + 2);
    a[0] = INF;
    For(i, 1, q) {
        a[i] -= VAL[i - 1];
        assert(LE[i - 1] == 0 && RI[i - 1] == n - 1);
    }
    a[q + 1] = 0;
    seg.build();
    For(i, 0, q + 1) seg.single_add(0, 0, q + 1, i, a[i]);

    vector<int> ans(n);
    For(i, 0, n - 1) {
        int c = C[i];
        int pos = search(q, c);
        if(a[pos] < 0) ans[i] = c - seg.max_suf(0, 0, q + 1, pos + 1).F;
        else           ans[i] = -seg.min_suf(0, 0, q + 1, pos + 1).F;
    }
    return vector<i32>(all(ans));
}

/*

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

0 4 13

*/

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