oj.uz

Submission #609643

# Submission time Handle Problem Language Result Execution time Memory
609643 2022-07-27T18:45:00 Z dxz05 Distributing Candies (IOI21_candies) C++17
0 / 100
 305 ms 27680 KB 
#include "candies.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll C;

struct SegTree{
    struct node{
        ll min;
        ll max;
        ll add;
        node(){
            min = max = add = 0;
        }
    };

    int size;
    vector<node> t;

    SegTree(int n){
        size = n;
        t.assign(4 * n + 2, node());
    }

    void push(int v){
        if (t[v].add == 0) return;

        t[v << 1].min += t[v].add;
        t[v << 1].max += t[v].add;
        t[v << 1].add += t[v].add;
        t[v << 1].max = min(t[v << 1].max, C);
        t[v << 1].min = min(t[v << 1].min, C);
        t[v << 1].max = max(t[v << 1].max, 0ll);
        t[v << 1].min = max(t[v << 1].min, 0ll);

        t[v << 1 | 1].min += t[v].add;
        t[v << 1 | 1].max += t[v].add;
        t[v << 1 | 1].add += t[v].add;
        t[v << 1 | 1].max = min(t[v << 1 | 1].max, C);
        t[v << 1 | 1].min = min(t[v << 1 | 1].min, C);
        t[v << 1 | 1].max = max(t[v << 1 | 1].max, 0ll);
        t[v << 1 | 1].min = max(t[v << 1 | 1].min, 0ll);

        t[v].add = 0;
    }

    void update(int v, int tl, int tr, int l, int r, int x){
        if (l <= tl && tr <= r){
            if (x > 0){
                if (t[v].max + x <= C){
                    t[v].min += x;
                    t[v].max += x;
                    t[v].add += x;
                    return;
                }
                if (t[v].min + x >= C){
                    t[v].min = t[v].max = C;
                    t[v].add += x;
                    return;
                }
            } else {
                if (t[v].min + x >= 0) {
                    t[v].min += x;
                    t[v].max += x;
                    t[v].add += x;
                    return;
                }
                if (t[v].max + x <= 0) {
                    t[v].min = t[v].max = 0;
                    t[v].add += x;
                    return;
                }
            }
        }
        if (tl > r || tr < l) return;

        push(v);

        int tm = (tl + tr) >> 1;

        update(v << 1, tl, tm, l, r, x);
        update(v << 1 | 1, tm + 1, tr, l, r, x);
        
        t[v].min = min(t[v << 1].min, t[v << 1 | 1].min);
        t[v].max = max(t[v << 1].max, t[v << 1 | 1].max);
    }

    int get(int v, int tl, int tr, int pos){
        if (tl == tr) return t[v].min;
        push(v);
        int tm = (tl + tr) >> 1;
        if (pos <= tm){
            return get(v << 1, tl, tm, pos);
        } else {
            return get(v << 1 | 1, tm + 1, tr, pos);
        }
    }

    void update(int l, int r, int x){
        update(1, 0, size - 1, l, r, x);
    }

    int get(int pos){
        return get(1, 0, size - 1, pos);
    }

};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q = l.size();
    C = c[0];

    SegTree st(n);

    for (int i = 0; i < q; i++){
        st.update(l[i], r[i], v[i]);
    }

    vector<int> ans(n, 2);
    for (int i = 0; i < n; i++) ans[i] = st.get(i);

    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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