제출 #924864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924864		Programmer123	사탕 분배 (IOI21_candies)	C++17	40 / 100	322 ms	51848 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>

typedef std::vector<int> ivec;
#define int long long
ivec c;
int N;

struct node {
    int min, max;
    node *left, *right;
    int maxV, maxC;
    int delta;
    enum Set {
        zero, cap, none
    } set;

    node(int l, int r) {
        min = l;
        max = r;
        maxV = 0;
        maxC = c[r - 1];
        delta = 0;
        set = none;
        if (r == l + 1) {
            left = right = nullptr;
            return;
        } else {
            left = new node(l, (l + r) / 2);
            right = new node((l + r) / 2, r);
        }
    }

    void add(int l, int r, int x) {
        l = std::max(l, min);
        r = std::min(r, max);
        if (l >= max || r <= min || l >= r) return;
        if (l == min && r == max) {
            delta += x;
            maxV += x;
            maxC -= x;
            return;
        }
        push(false);
        left->add(l, r, x);
        right->add(l, r, x);
        maxV = std::max(left->maxV, right->maxV) + delta;
        maxC = std::max(left->maxC, right->maxC) - delta;
    }

    void push(bool d) {
        if (set == zero) {
            left->set0(min, max);
            right->set0(min, max);
            set = none;
        }
        if (set == cap) {
            left->setc(min, max);
            right->setc(min, max);
            set = none;
        }
        if (d) {
            if (delta != 0) {
                left->add(min, max, delta);
                right->add(min, max, delta);
                delta = 0;
            }
        }
    }

    void set0(int l, int r) {
        l = std::max(l, min);
        r = std::min(r, max);
        if (l >= max || r <= min || l >= r) return;
        if (l == min && r == max) {
            set = zero;
            maxV = 0;
            maxC = c[r - 1];
            delta = 0;
            return;
        }
        if (set == zero && delta == 0) return;
        push(true);
        left->set0(l, r);
        right->set0(l, r);
        maxV = std::max(left->maxV, right->maxV);
        maxC = std::max(left->maxC, right->maxC);
    }

    void setc(int l, int r) {
        l = std::max(l, min);
        r = std::min(r, max);
        if (l >= max || r <= min || l >= r) return;
        if (l == min && r == max) {
            set = cap;
            maxV = c[r - 1];
            maxC = 0;
            delta = 0;
            return;
        }
        if (set == cap && delta == 0) return;
        push(true);
        left->setc(l, r);
        right->setc(l, r);
        maxV = std::max(left->maxV, right->maxV);
        maxC = std::max(left->maxC, right->maxC);
    }

    int pfxC(int x) {
        if (maxC <= x) return max;
        if (max == min + 1) return min;
        push(true);
        if (left->maxC > x) return left->pfxC(x + delta);
        return right->pfxC(x + delta);
    }

    int pfxV(int x) {
        if (maxV <= x) return max;
        if (max == min + 1) return min;
        push(true);
        if (left->maxV > x) return left->pfxV(x - delta);
        return right->pfxV(x - delta);
    }

    int query(int x) const {
        if (x < min || x >= max) return 0;
        if (set == zero) return delta;
        if (set == cap) return c[x] + delta;
        if (max == min + 1) return delta;
        return left->query(x) + right->query(x) + delta;
    }
};

ivec distribute_candies(ivec _c, ivec l,
                        ivec r, ivec v) {
    c = std::move(_c);
    N = c.size();
    int Q = l.size();
    ivec ans(N);
    bool complete = true;
    for (int i = 0; i < Q; ++i) {
        if (l[i] != 0 || r[i] != N - 1) complete = false;
    }
    if (complete) {
        ivec realC = c;
        std::sort(c.begin(), c.end());
        std::map<int, int> posmap;
        for (int i = 0; i < N; ++i) {
            posmap[c[i]] = i;
        }
        node tree(0, N);
        for (int i = 0; i < Q; ++i) {
            if (v[i] > 0) {
                int pre = tree.pfxC(v[i]);
                tree.setc(0, pre);
                tree.add(pre, N, v[i]);
            } else if (v[i] < 0) {
                int pre = tree.pfxV(-v[i]);
                tree.set0(0, pre);
                tree.add(pre, N, v[i]);
            }
#ifdef LOCAL
            std::cout << "Applied operation, tree is now:";
            for (int j = 0; j < N; ++j) {
                std::cout << " " << tree.query(j);
            }
            std::cout << std::endl;
#endif
        }
        for (int i = 0; i < N; ++i) {
            ans[i] = tree.query(posmap[realC[i]]);
        }
        return ans;
    }
    if (N * Q <= 2000 * 2000) {
        for (int i = 0; i < N; ++i) {
            int val = 0;
            for (int j = 0; j < Q; ++j) {
                if (l[j] > i || r[j] < i) continue;
                val += v[j];
                if (val < 0) val = 0;
                if (val > c[i]) val = c[i];
            }
            ans[i] = val;
        }
        return ans;
    }
    bool pos = true;
    for (int i = 0; i < Q; ++i) {
        if (v[i] < 0) pos = false;
    }
    if (pos) {
        int diff[N + 1];
        for (int i = 0; i <= N; ++i) {
            diff[i] = 0;
        }
        for (int i = 0; i < Q; ++i) {
            diff[l[i]] += v[i];
            diff[r[i] + 1] -= v[i];
        }
        for (int i = 1; i <= N; ++i) {
            diff[i] += diff[i - 1];
        }
        for (int i = 0; i < N; ++i) {
            ans[i] = (signed) std::min<int>(diff[i], c[i]);
        }
        return ans;
    }
    assert(false);
}

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