oj.uz

Submission #786544

# Submission time Handle Problem Language Result Execution time Memory
786544 2023-07-18T08:59:48 Z boris_mihov Distributing Candies (IOI21_candies) C++17
100 / 100
 708 ms 55996 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 34632 KB Output is correct
2 Correct 13 ms 34660 KB Output is correct
3 Correct 13 ms 34840 KB Output is correct
4 Correct 14 ms 34748 KB Output is correct
5 Correct 15 ms 34900 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 54212 KB Output is correct
2 Correct 681 ms 53440 KB Output is correct
3 Correct 662 ms 53276 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 34644 KB Output is correct
2 Correct 185 ms 46372 KB Output is correct
3 Correct 199 ms 40576 KB Output is correct
4 Correct 692 ms 55284 KB Output is correct
5 Correct 708 ms 55676 KB Output is correct
6 Correct 580 ms 55996 KB Output is correct
7 Correct 568 ms 55412 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 34668 KB Output is correct
2 Correct 13 ms 34644 KB Output is correct
3 Correct 88 ms 45356 KB Output is correct
4 Correct 167 ms 38488 KB Output is correct
5 Correct 458 ms 47912 KB Output is correct
6 Correct 501 ms 48548 KB Output is correct
7 Correct 391 ms 49176 KB Output is correct
8 Correct 454 ms 47816 KB Output is correct
9 Correct 495 ms 49296 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 34632 KB Output is correct
2 Correct 13 ms 34660 KB Output is correct
3 Correct 13 ms 34840 KB Output is correct
4 Correct 14 ms 34748 KB Output is correct
5 Correct 15 ms 34900 KB Output is correct
6 Correct 586 ms 54212 KB Output is correct
7 Correct 681 ms 53440 KB Output is correct
8 Correct 662 ms 53276 KB Output is correct
9 Correct 13 ms 34644 KB Output is correct
10 Correct 185 ms 46372 KB Output is correct
11 Correct 199 ms 40576 KB Output is correct
12 Correct 692 ms 55284 KB Output is correct
13 Correct 708 ms 55676 KB Output is correct
14 Correct 580 ms 55996 KB Output is correct
15 Correct 568 ms 55412 KB Output is correct
16 Correct 15 ms 34668 KB Output is correct
17 Correct 13 ms 34644 KB Output is correct
18 Correct 88 ms 45356 KB Output is correct
19 Correct 167 ms 38488 KB Output is correct
20 Correct 458 ms 47912 KB Output is correct
21 Correct 501 ms 48548 KB Output is correct
22 Correct 391 ms 49176 KB Output is correct
23 Correct 454 ms 47816 KB Output is correct
24 Correct 495 ms 49296 KB Output is correct
25 Correct 13 ms 34644 KB Output is correct
26 Correct 171 ms 38460 KB Output is correct
27 Correct 195 ms 46004 KB Output is correct
28 Correct 669 ms 53920 KB Output is correct
29 Correct 634 ms 54348 KB Output is correct
30 Correct 640 ms 54496 KB Output is correct
31 Correct 684 ms 54704 KB Output is correct
32 Correct 596 ms 54908 KB Output is correct