제출 #786544

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

candies

#include "candies.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 200000 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;

int n, q;
struct SegmentTree
{
    struct Node
    {
        llong minPrefix;
        llong maxPrefix;
        int minIdx;
        int maxIdx;
        llong sum;
        Node()
        {
            sum = -INF;
        }
    };

    Node tree[4*MAXN];
    Node combine(Node left, Node right)
    {
        if (left.sum == -INF)
        {
            return right;
        }

        Node res;
        res.sum = left.sum + right.sum;
        if (left.minPrefix < left.sum + right.minPrefix)
        {
            res.minPrefix = left.minPrefix;
            res.minIdx = left.minIdx;
        } else
        {
            res.minPrefix = left.sum + right.minPrefix;
            res.minIdx = right.minIdx;
        }

        if (left.maxPrefix > left.sum + right.maxPrefix)
        {
            res.maxPrefix = left.maxPrefix;
            res.maxIdx = left.maxIdx;
        } else
        {
            res.maxPrefix = left.sum + right.maxPrefix;
            res.maxIdx = right.maxIdx;
        }

        return res;
    }

    void build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node].minIdx = tree[node].maxIdx = l;
            tree[node].minPrefix = tree[node].maxPrefix = tree[node].sum = 0;
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node);
        build(mid + 1, r, 2*node + 1);
        tree[node] = combine(tree[2*node], tree[2*node + 1]);
    }

    void update(int l, int r, int node, int queryPos, int queryVal)
    {
        if (l == r)
        {
            tree[node].minIdx = tree[node].maxIdx = l;
            tree[node].minPrefix = tree[node].maxPrefix = tree[node].sum = queryVal;
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
        else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
        tree[node] = combine(tree[2*node], tree[2*node + 1]);
    }

    Node query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        Node res;
        int mid = (l + r) / 2;
        if (queryL <= mid) res = combine(res, query(l, mid, 2*node, queryL, queryR));
        if (mid + 1 <= queryR) res = combine(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
        return res;
    }

    void build()
    {
        build(1, q + 2, 1);
    }

    void update(int pos, int val)
    {
        update(1, q + 2, 1, pos, val);
    }

    Node query(int l, int r)
    {
        return query(1, q + 2, 1, l, r);
    }
};

SegmentTree tree;
std::vector <std::pair <int,int>> activate[MAXN];
std::vector <int> deactivate[MAXN];

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

    activate[0].push_back({INTINF, 1});
    activate[0].push_back({-INTINF, 2});
    for (int i = 0 ; i < q ; ++i)
    {
        activate[l[i]].push_back({v[i], i + 3});
        deactivate[r[i] + 1].push_back(i + 3);
    }

    tree.build();
    std::vector <int> ans(n);
    for (int i = 0 ; i < n ; ++i)
    {
        for (const auto &[val, pos] : activate[i])
        {
            tree.update(pos, val);
        }

        for (const int &pos : deactivate[i])
        {
            tree.update(pos, 0);
        }
    
        int l = 1, r = q + 3, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            SegmentTree::Node res = tree.query(mid, q + 2);
            if (res.maxPrefix - res.minPrefix >= c[i]) l = mid;
            else r = mid;
        }

        SegmentTree::Node res = tree.query(l, q + 2);
        if (res.maxIdx > res.minIdx)
        {
            llong lowerBound = tree.query(1, res.maxIdx).sum - c[i];
            ans[i] = tree.tree[1].sum - lowerBound;
        } else
        {
            llong lowerBound = tree.query(1, res.minIdx).sum;
            ans[i] = tree.tree[1].sum - lowerBound;
        }
    }

    return ans;
}

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