oj.uz

Submission #590161

# Submission time Handle Problem Language Result Execution time Memory
590161 2022-07-05T15:22:39 Z Drew_ Distributing Candies (IOI21_candies) C++17
100 / 100
 494 ms 38100 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12500 KB Output is correct
2 Correct 10 ms 12600 KB Output is correct
3 Correct 12 ms 12724 KB Output is correct
4 Correct 9 ms 12768 KB Output is correct
5 Correct 9 ms 12792 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 35100 KB Output is correct
2 Correct 371 ms 35464 KB Output is correct
3 Correct 377 ms 35304 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12540 KB Output is correct
2 Correct 264 ms 24896 KB Output is correct
3 Correct 93 ms 21936 KB Output is correct
4 Correct 452 ms 37220 KB Output is correct
5 Correct 494 ms 37732 KB Output is correct
6 Correct 431 ms 38100 KB Output is correct
7 Correct 375 ms 37448 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12500 KB Output is correct
2 Correct 6 ms 12592 KB Output is correct
3 Correct 111 ms 23324 KB Output is correct
4 Correct 62 ms 20916 KB Output is correct
5 Correct 204 ms 30916 KB Output is correct
6 Correct 186 ms 31680 KB Output is correct
7 Correct 166 ms 32160 KB Output is correct
8 Correct 202 ms 30920 KB Output is correct
9 Correct 155 ms 32340 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12500 KB Output is correct
2 Correct 10 ms 12600 KB Output is correct
3 Correct 12 ms 12724 KB Output is correct
4 Correct 9 ms 12768 KB Output is correct
5 Correct 9 ms 12792 KB Output is correct
6 Correct 365 ms 35100 KB Output is correct
7 Correct 371 ms 35464 KB Output is correct
8 Correct 377 ms 35304 KB Output is correct
9 Correct 8 ms 12540 KB Output is correct
10 Correct 264 ms 24896 KB Output is correct
11 Correct 93 ms 21936 KB Output is correct
12 Correct 452 ms 37220 KB Output is correct
13 Correct 494 ms 37732 KB Output is correct
14 Correct 431 ms 38100 KB Output is correct
15 Correct 375 ms 37448 KB Output is correct
16 Correct 7 ms 12500 KB Output is correct
17 Correct 6 ms 12592 KB Output is correct
18 Correct 111 ms 23324 KB Output is correct
19 Correct 62 ms 20916 KB Output is correct
20 Correct 204 ms 30916 KB Output is correct
21 Correct 186 ms 31680 KB Output is correct
22 Correct 166 ms 32160 KB Output is correct
23 Correct 202 ms 30920 KB Output is correct
24 Correct 155 ms 32340 KB Output is correct
25 Correct 7 ms 12500 KB Output is correct
26 Correct 62 ms 20976 KB Output is correct
27 Correct 235 ms 24440 KB Output is correct
28 Correct 393 ms 35968 KB Output is correct
29 Correct 428 ms 36340 KB Output is correct
30 Correct 394 ms 36556 KB Output is correct
31 Correct 383 ms 36724 KB Output is correct
32 Correct 446 ms 36920 KB Output is correct