제출 #590161

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

candies

#include "candies.h"

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define f1 first
#define s2 second

using ii = pair<int, int>;
using ll = long long;
using pl = pair<ll, ll>;

const int MAX = 2e5 + 69;
const ll inf = (ll)1e18 + 69;

struct Segtree
{
    struct Node
    {
        ll sum, pmx, pmn; // subarray sum, prefix maximum, prefix minimum
        
        Node() : sum(0), pmx(0), pmn(0) {}
        Node(ll val) : sum(val), pmx(max(0ll, val)), pmn(min(0ll, val)) {}
        
        friend Node operator+ (const Node &lhs, const Node &rhs)
        {
            Node res;
            res.sum = lhs.sum + rhs.sum;
            res.pmx = max(lhs.pmx, lhs.sum + rhs.pmx);
            res.pmn = min(lhs.pmn, lhs.sum + rhs.pmn);
            return res;
        }
    };

    int n;
    Node st[1 << 19];

    Segtree() {}
    Segtree(int n_) : n(n_) {}

    inline void modify(int p, ll val)
    {
        const auto modify_ = [&](const auto &self, int node, int l, int r) -> void
        {
            if (l > p || r < p)
                return;
            if (p <= l && r <= p)
            {
                st[node] = Node(val);
                return;
            }
            int mid = (l + r) >> 1;
            self(self, node << 1, l, mid);
            self(self, node << 1 | 1, mid+1, r);
            st[node] = st[node << 1] + st[node << 1 | 1];
        };
        modify_(modify_, 1, 0, n-1);
    }

    inline ll query(ll C) 
    {
        const auto query_ = [&](const auto &self, int node, int l, int r) -> ll
        {
            if (l == r)
                return max(min(C, st[node].sum), 0ll);

            int mid = (l + r) >> 1; 
            if (st[node << 1 | 1].pmx - st[node << 1 | 1].pmn > C) // will reach the bound in later indices
                return self(self, node << 1 | 1, mid+1, r);
            ll res = self(self, node << 1, l, mid);

            if (res + st[node << 1 | 1].pmx > C) // will go > C, the candies will be C until the prefix maximum
                return C - (st[node << 1 | 1].pmx - st[node << 1 | 1].sum);
            if (res + st[node << 1 | 1].pmn < 0) // will go < 0, the candies will go negative until the prefix minimum
                return st[node << 1 | 1].sum - st[node << 1 | 1].pmn;
            return res + st[node << 1 | 1].sum;
        };
        return query_(query_, 1, 0, n-1);
    }
};

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> val) 
{
    int N = (int)C.size(), Q = (int)L.size();


    vector<vector<ii>> op(N+1);
    for (int i = 0; i < Q; ++i)
    {
        op[L[i]].pb({i, val[i]});
        op[R[i]+1].pb({i, 0});
    }

    Segtree st = Segtree(Q);

    vector<int> res(N);
    for (int i = 0; i < N; ++i)
    {
        for (auto [id, v] : op[i])
            st.modify(id, v);
        res[i] = (int)st.query(C[i]);
    }

    return res;
}

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