oj.uz

Submission #813796

# Submission time Handle Problem Language Result Execution time Memory
813796 2023-08-08T03:52:14 Z PixelCat Distributing Candies (IOI21_candies) C++17
29 / 100
 530 ms 34112 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19028 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 69 ms 16332 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19092 KB Output is correct
2 Correct 8 ms 19028 KB Output is correct
3 Correct 75 ms 25380 KB Output is correct
4 Correct 187 ms 23056 KB Output is correct
5 Correct 487 ms 29260 KB Output is correct
6 Correct 530 ms 33448 KB Output is correct
7 Correct 460 ms 34028 KB Output is correct
8 Correct 482 ms 32672 KB Output is correct
9 Correct 492 ms 34112 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19028 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -