oj.uz

Submission #1021136

# Submission time Handle Problem Language Result Execution time Memory
1021136 2024-07-12T14:43:49 Z mdn2002 Distributing Candies (IOI21_candies) C++17
8 / 100
 535 ms 1305424 KB 
/*
Mayoeba Yabureru
*/
#include<bits/stdc++.h>
using namespace std;

struct Node {
    int valuel = 0, valuer = 0, lazyadd = 0, lazyset = -1;
    int left = -1, right = -1;
    Node() {}
};
Node st[55000006];
int cnt;
void push(int node, int l, int r) {
    int left = st[node].left, right = st[node].right;
    if (st[node].lazyset != -1) {
        //cout << '*' << l << ' ' << r << ' ' << st[node].lazyset << ' ' << st[node].lazyadd << endl;
        if (st[node].lazyset == 0) {
            st[node].valuel = 0;
            st[node].valuer = 0;
        }
        else {
            st[node].valuel = l;
            st[node].valuer = r;
        }
        st[node].valuel += st[node].lazyadd;
        st[node].valuer += st[node].lazyadd;
        if (l != r) {
            st[left].lazyset = st[right].lazyset = st[node].lazyset;
            st[left].lazyadd = st[right].lazyadd = 0;
            st[left].lazyadd += st[node].lazyadd;
            st[right].lazyadd += st[node].lazyadd;
        }
        st[node].lazyset = -1;
        st[node].lazyadd = 0;
    }
    else if (st[node].lazyadd != 0) {
        st[left].lazyadd += st[node].lazyadd;
        st[right].lazyadd += st[node].lazyadd;
        st[node].valuel += st[node].lazyadd;
        st[node].valuer += st[node].lazyadd;
        st[node].lazyadd = 0;
    }
}
void update(int node, int l, int r, int val) {
    if (st[node].left == -1) {
        st[node].left = ++ cnt;
        st[cnt] = Node();
    }
    if (st[node].right == -1) {
        st[node].right = ++ cnt;
        st[cnt] = Node();
    }
    //cout << ' ' << l << ' ' << r << ' ' << st[node].lazyset << endl;
    push(node, l, r);
    long long vall = st[node].valuel, valr = st[node].valuer;
    //cout << ' ' << l << ' ' << r << ' ' << vall << ' ' << valr << ' ' << val << endl;

    if (val >= 0 && vall + val > l && valr + val > r) { // all the boxes with cap inbetween l and r are set to equal the cap
        st[node].lazyadd = 0;
        st[node].lazyset = 1;
        push(node, l, r);
        return;
    }

    if (val >= 0 && vall + val <= l && valr + val <= r) { // all the boxes with cap inbetween l and r are added val
        st[node].lazyadd = val;
        push(node, l, r);
        return;
    }

    if (val < 0 && vall + val < 0 && valr + val < 0) { // all the boxes with cap inbetween l and r are set to equal the 0
        st[node].lazyadd = 0;
        st[node].lazyset = 0;
        push(node, l, r);
        return;
    }

    if (val < 0 && vall + val >= 0 && valr + val >= 0) { // all the boxes with cap inbetween l and r are added val
        st[node].lazyadd = val;
        push(node, l, r);
        return;
    }

    int mid = (l + r) / 2;

    int left = st[node].left, right = st[node].right;
    update(left, l, mid, val);
    update(right, mid + 1, r, val);
    st[node].valuel = st[left].valuel;
    st[node].valuer = st[right].valuer;
}

int query(int node, int l, int r, int x) {
    if (st[node].left == -1) {
        st[node].left = ++ cnt;
        st[cnt] = Node();
    }
    if (st[node].right == -1) {
        st[node].right = ++ cnt;
        st[cnt] = Node();
    }
    push(node, l, r);
    if (l == x && r == x) return st[node].valuel;
    int mid = (l + r) / 2;
    if (x <= mid) return query(st[node].left, l, mid, x);
    return query(st[node].right, mid + 1, r, x);
}

vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    st[0] = Node();
    vector<int> s(n);
    vector<long long> sum(n + 2);
    for (int i = 0; i < v.size(); i ++) {
        sum[l[i]] += v[i];
        sum[r[i] + 1] -= v[i];
    }
    for (int i = 0; i < n; i ++) {
        if (i) sum[i] += sum[i - 1];
        if (sum[i] > c[i]) s[i] = c[i];
        else s[i] = sum[i];
    }
    return s;
}

/*
3
10 15 13
2
0 2 20
0 2 -11
*/

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:116:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for (int i = 0; i < v.size(); i ++) {
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 1291856 KB Output is correct
2 Incorrect 465 ms 1291920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 1305424 KB Output is correct
2 Correct 518 ms 1304680 KB Output is correct
3 Correct 518 ms 1304388 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 450 ms 1291996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 450 ms 1291856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 1291856 KB Output is correct
2 Incorrect 465 ms 1291920 KB Output isn't correct
3 Halted 0 ms 0 KB -