oj.uz

Submission #809032

# Submission time Handle Problem Language Result Execution time Memory
809032 2023-08-05T14:24:13 Z puppy Distributing Candies (IOI21_candies) C++17
100 / 100
 1428 ms 41516 KB 
#include "candies.h"
#include <vector>
#include <cmath>
//#include <iostream>
#define int long long
using namespace std;

const int inf = 1e18;

struct Node
{
    int mx, mn;
    Node operator+(const Node &nd) const {
        return {max(mx, nd.mx), min(mn, nd.mn)};
    }
};
const Node zero = {-inf, inf};

struct SegTree
{
    vector<Node> tree;
    vector<int> lazy;
    SegTree(int N)
    {
        int sz = 1 << ((int)ceil(log2(N+1)) + 1);
        tree.resize(sz); lazy.resize(sz);
    }
    void push(int s, int e, int node)
    {
        tree[node].mx += lazy[node];
        tree[node].mn += lazy[node];
        if (s != e) {
            for (int i:{2*node, 2*node+1}) {
                lazy[i] += lazy[node];
            }
        }
        lazy[node] = 0;
    }
    void upd(int s, int e, int node, int l, int r, int x)
    {
        push(s, e, node);
        if (e < l || r < s) return;
        if (l <= s && e <= r) {
            lazy[node] += x;
            push(s, e, node);
            return;
        }
        upd(s, (s+e)/2, 2*node, l, r, x);
        upd((s+e)/2+1, e, 2*node+1, l, r, x);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }
    Node query(int s, int e, int node, int l, int r)
    {
        push(s, e, node);
        if (e < l || r < s) return zero;
        if (l <= s && e <= r) return tree[node];
        return query(s, (s+e)/2, 2*node, l, r) + query((s+e)/2+1, e, 2*node+1, l, r);
    }
};

vector<pair<int, int>> upd[200005];

std::vector<signed> distribute_candies(std::vector<signed> c, std::vector<signed> l,
                                    std::vector<signed> r, std::vector<signed> v) {
    int N = c.size();
    int Q = l.size();
    SegTree seg(Q+1);
    for (int i = 0; i < Q; i++) {
        upd[l[i]].push_back(make_pair(i+1, v[i]));
        upd[r[i]+1].push_back(make_pair(i+1, -v[i]));
    }
    vector<signed> ans(N);
    for (int i = 0; i < N; i++) {
        for (pair<int, int> p: upd[i]) {
            seg.upd(0, Q, 1, p.first, Q, p.second);
        }
        Node tmp = seg.query(0, Q, 1, 0, Q);
        if (tmp.mx - tmp.mn <= c[i]) {
            ans[i] = seg.query(0, Q, 1, Q, Q).mx - seg.query(0, Q, 1, 0, Q).mn;
        }
        else {
            int l = 0, r = Q;
            while (l < r) {
                int m = l + r + 1 >> 1;
                Node tmp = seg.query(0, Q, 1, m, Q);
                if (tmp.mx - tmp.mn <= c[i]) r = m - 1;
                else l = m;
            }
            Node cur = seg.query(0, Q, 1, l, l), nxt = seg.query(0, Q, 1, l+1, l+1);
            if (cur.mx > nxt.mx) {
                ans[i] = seg.query(0, Q, 1, Q, Q).mx - seg.query(0, Q, 1, l+1, Q).mn;
            }
            else {
                ans[i] = c[i] - (seg.query(0, Q, 1, l+1, Q).mx - seg.query(0, Q, 1, Q, Q).mx);
            }
        }
    }
    return ans;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:84:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |                 int m = l + r + 1 >> 1;
      |                         ~~~~~~^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4980 KB Output is correct
3 Correct 4 ms 5156 KB Output is correct
4 Correct 4 ms 5252 KB Output is correct
5 Correct 7 ms 5204 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1279 ms 37136 KB Output is correct
2 Correct 1392 ms 39052 KB Output is correct
3 Correct 1177 ms 38724 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 259 ms 33912 KB Output is correct
3 Correct 288 ms 10920 KB Output is correct
4 Correct 1244 ms 40736 KB Output is correct
5 Correct 1250 ms 41128 KB Output is correct
6 Correct 1379 ms 41516 KB Output is correct
7 Correct 1354 ms 40856 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 120 ms 31060 KB Output is correct
4 Correct 295 ms 8892 KB Output is correct
5 Correct 900 ms 34144 KB Output is correct
6 Correct 1078 ms 34812 KB Output is correct
7 Correct 1122 ms 35400 KB Output is correct
8 Correct 795 ms 34036 KB Output is correct
9 Correct 1113 ms 35520 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4980 KB Output is correct
3 Correct 4 ms 5156 KB Output is correct
4 Correct 4 ms 5252 KB Output is correct
5 Correct 7 ms 5204 KB Output is correct
6 Correct 1279 ms 37136 KB Output is correct
7 Correct 1392 ms 39052 KB Output is correct
8 Correct 1177 ms 38724 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 259 ms 33912 KB Output is correct
11 Correct 288 ms 10920 KB Output is correct
12 Correct 1244 ms 40736 KB Output is correct
13 Correct 1250 ms 41128 KB Output is correct
14 Correct 1379 ms 41516 KB Output is correct
15 Correct 1354 ms 40856 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 120 ms 31060 KB Output is correct
19 Correct 295 ms 8892 KB Output is correct
20 Correct 900 ms 34144 KB Output is correct
21 Correct 1078 ms 34812 KB Output is correct
22 Correct 1122 ms 35400 KB Output is correct
23 Correct 795 ms 34036 KB Output is correct
24 Correct 1113 ms 35520 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 233 ms 8808 KB Output is correct
27 Correct 193 ms 33516 KB Output is correct
28 Correct 1028 ms 39388 KB Output is correct
29 Correct 1186 ms 39672 KB Output is correct
30 Correct 1276 ms 39936 KB Output is correct
31 Correct 1409 ms 40140 KB Output is correct
32 Correct 1428 ms 40332 KB Output is correct