oj.uz

Submission #813802

# Submission time Handle Problem Language Result Execution time Memory
813802 2023-08-08T03:57:41 Z PixelCat Distributing Candies (IOI21_candies) C++17
100 / 100
 730 ms 46024 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, 0);
    a[0] = INF;
    seg.build();
    seg.single_add(0, 0, q + 1, 0, a[0]);

    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();
            a[e.pos] += e.val;
            seg.single_add(0, 0, q + 1, e.pos, e.val);
        }
        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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19028 KB Output is correct
2 Correct 8 ms 19028 KB Output is correct
3 Correct 8 ms 19284 KB Output is correct
4 Correct 9 ms 19328 KB Output is correct
5 Correct 11 ms 19320 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 39388 KB Output is correct
2 Correct 730 ms 43336 KB Output is correct
3 Correct 729 ms 43224 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19028 KB Output is correct
2 Correct 178 ms 37728 KB Output is correct
3 Correct 182 ms 23248 KB Output is correct
4 Correct 698 ms 39268 KB Output is correct
5 Correct 632 ms 45600 KB Output is correct
6 Correct 684 ms 46024 KB Output is correct
7 Correct 701 ms 45392 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18988 KB Output is correct
2 Correct 9 ms 19064 KB Output is correct
3 Correct 95 ms 37724 KB Output is correct
4 Correct 187 ms 23296 KB Output is correct
5 Correct 524 ms 39388 KB Output is correct
6 Correct 551 ms 39272 KB Output is correct
7 Correct 517 ms 39304 KB Output is correct
8 Correct 512 ms 39400 KB Output is correct
9 Correct 484 ms 39392 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19028 KB Output is correct
2 Correct 8 ms 19028 KB Output is correct
3 Correct 8 ms 19284 KB Output is correct
4 Correct 9 ms 19328 KB Output is correct
5 Correct 11 ms 19320 KB Output is correct
6 Correct 695 ms 39388 KB Output is correct
7 Correct 730 ms 43336 KB Output is correct
8 Correct 729 ms 43224 KB Output is correct
9 Correct 8 ms 19028 KB Output is correct
10 Correct 178 ms 37728 KB Output is correct
11 Correct 182 ms 23248 KB Output is correct
12 Correct 698 ms 39268 KB Output is correct
13 Correct 632 ms 45600 KB Output is correct
14 Correct 684 ms 46024 KB Output is correct
15 Correct 701 ms 45392 KB Output is correct
16 Correct 7 ms 18988 KB Output is correct
17 Correct 9 ms 19064 KB Output is correct
18 Correct 95 ms 37724 KB Output is correct
19 Correct 187 ms 23296 KB Output is correct
20 Correct 524 ms 39388 KB Output is correct
21 Correct 551 ms 39272 KB Output is correct
22 Correct 517 ms 39304 KB Output is correct
23 Correct 512 ms 39400 KB Output is correct
24 Correct 484 ms 39392 KB Output is correct
25 Correct 8 ms 19028 KB Output is correct
26 Correct 222 ms 24400 KB Output is correct
27 Correct 184 ms 40360 KB Output is correct
28 Correct 696 ms 43820 KB Output is correct
29 Correct 654 ms 44236 KB Output is correct
30 Correct 656 ms 44488 KB Output is correct
31 Correct 623 ms 44708 KB Output is correct
32 Correct 632 ms 45000 KB Output is correct