제출 #515975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
515975		apostoldaniel854	사탕 분배 (IOI21_candies)	C++17	100 / 100	368 ms	43272 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define dbg(x) cerr << #x << " " << x << "\n

struct node_info {
    ll sum;
    ll sum_max;
    ll sum_min;
};

class SegTree {
private:
    vector <node_info> seg;
    node_info join(node_info L, node_info R) {
        node_info RES;
        RES.sum = L.sum + R.sum;
        RES.sum_max = max(L.sum_max, R.sum_max + L.sum);
        RES.sum_min = min(L.sum_min, R.sum_min + L.sum);
        return RES;
    }
public:
    SegTree(int n) {
        seg.resize(1 + 4 * n);
    }
    void update_pos(int node, int lb, int rb, int pos, int val) {
        if (lb == rb) {
            seg[node].sum_max = max(0, val);
            seg[node].sum_min = min(0, val);
            seg[node].sum = val;
            return;
        }
        int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1;
        if (pos <= mid)
            update_pos(lnode, lb, mid, pos, val);
        else
            update_pos(rnode, mid + 1, rb, pos, val);
        seg[node] = join(seg[lnode], seg[rnode]);
    }
    ll go(int node, int lb, int rb, ll cap) {
        if (lb == rb)
            return min(max(seg[node].sum, 0ll), cap);
        int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1;
        if (seg[rnode].sum_max - seg[rnode].sum_min > cap)
            return go(rnode, mid + 1, rb, cap);
        ll value = go(lnode, lb, mid, cap);
        if (value + seg[rnode].sum_max > cap)
            return cap - (seg[rnode].sum_max - seg[rnode].sum);
        if (value + seg[rnode].sum_min < 0)
            return seg[rnode].sum - seg[rnode].sum_min;
        return value + seg[rnode].sum;
    }
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size(), q = v.size();
    vector <vector <int>> L(n), R(n);
    for (int i = 0; i < q; i++) {
        L[l[i]].push_back(i + 1);
        if (r[i] + 1 < n)
            R[r[i] + 1].push_back(i + 1);
    }
    SegTree DS_time(q);
    std::vector<int> s(n);
    for (int i = 0; i < n; i++) {
        for (int id : L[i]) {
            /// activate id
            DS_time.update_pos(1, 1, q, id, v[id - 1]);
        }
        for (int id : R[i]) {
            /// deactivate id
            DS_time.update_pos(1, 1, q, id, 0);
        }
        s[i] = DS_time.go(1, 1, q, c[i]);
    }
    return s;
}
/**
3
10 15 13
2
0 2 20
0 1 -11

**/

컴파일 시 표준 에러 (stderr) 메시지

candies.cpp:7:42: warning: missing terminating " character
    7 | #define dbg(x) cerr << #x << " " << x << "\n
      |                                          ^

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