제출 #1022686

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022686		Wael	Distributing Candies (IOI21_candies)	C++17	100 / 100	377 ms	43256 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
using i64 = long long;

struct SegmentTree {
    int n;
    struct Node {
        i64 lazy, mn, mx;
        Node() {
            lazy = 0;
            mn = mx = 0;
        }
    };

    vector<Node> st;
    SegmentTree(int n) : n(n) {
        st.resize(4 * n);
    }

    void push(int node) {
        st[2 * node + 1].lazy += st[node].lazy;
        st[2 * node + 2].lazy += st[node].lazy;
        st[2 * node + 1].mn += st[node].lazy;
        st[2 * node + 2].mn += st[node].lazy;
        st[2 * node + 1].mx += st[node].lazy;
        st[2 * node + 2].mx += st[node].lazy;
        st[node].lazy = 0;
    }

    void update(int l, int r, int x) {
        update(l, r, x, 0, 0, n - 1);
    }
    void update(int l, int r,  int x, int node, int lx, int rx) {
        if (lx > r || rx < l) return;
        if (l <= lx && rx <= r) {
            st[node].lazy += x;
            st[node].mn += x;
            st[node].mx += x;
            return;
        }
        push(node);
        int mid = (lx + rx) / 2;
        update(l, r, x, 2 * node + 1, lx, mid);
        update(l, r, x, 2 * node + 2, mid + 1, rx);
        st[node].mn = min(st[2 * node + 1].mn, st[2 * node + 2].mn);
        st[node].mx = max(st[2 * node + 1].mx, st[2 * node + 2].mx);
    }

    array<i64, 3> getSuffix(int c) {
        return getSuffix(c, 1e18, -1e18, 0, 0, n - 1);
    }
    array<i64, 3> getSuffix(int c, i64 mn, i64 mx, int node, int lx, int rx) {
        if (lx == rx) return {lx, mn, mx};
        push(node);

        int mid = (lx + rx) / 2;
        i64 newMx = max(mx, st[2 * node + 2].mx);
        i64 newMn = min(mn, st[2 * node + 2].mn);
        if (newMx - newMn > c) {
            return getSuffix(c, mn, mx, 2 * node + 2, mid + 1, rx);
        } else {
            return getSuffix(c, newMn, newMx, 2 * node + 1, lx, mid);
        }
    }

    i64 get(int i) {
        return get(i, 0, 0, n - 1);
    }
    i64 get(int i, int node, int lx, int rx) {
        if (lx == rx) return st[node].mn;
        push(node);
        int mid = (lx + rx) / 2;
        if (i <= mid) {
            return get(i, 2 * node + 1, lx, mid);
        } else {
            return get(i, 2 * node + 2, mid + 1, rx);
        }
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
    int q = v.size();

    vector<vector<int>> query(n);
    for (int i = 0; i < q; ++i) {
        query[l[i]].push_back(i);
        if (r[i] + 1 < n) {
            query[r[i] + 1].push_back(i);
        }
    }

    vector<int> s(n);
    SegmentTree st(q + 1);
    for (int i = 0; i < n; ++i) {
        for (auto j : query[i]) {
            if (l[j] == i) {
                st.update(j + 1, q, v[j]);
            } else {
                st.update(j + 1, q, -v[j]);
            }
        }
        i64 ans = st.get(q);
        if (st.st[0].mn >= 0 && st.st[0].mx <= c[i]) {
            s[i] = ans;
        } else {
            auto [j, mn, mx] = st.getSuffix(c[i]);
            if (st.get(j) < mn) {
                s[i] = c[i] - (mx - ans);
            } else {
                s[i] = ans - mn;
            }
        }
    }

    return s;
}

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