oj.uz

Submission #609681

# Submission time Handle Problem Language Result Execution time Memory
609681 2022-07-27T19:15:12 Z dxz05 Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 25316 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 | 1].min += t[v].add;
        t[v << 1 | 1].max += t[v].add;
        t[v << 1 | 1].add += t[v].add;

        t[v].add = 0;
    }

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

            if (tl == tr) {
                t[v].min = t[v].max = C;
                t[v].add = 0;
                return;
            }

            if (t[v].min > C) {
                t[v].add += C - t[v].min;
                t[v].max += C - t[v].min;
                t[v].min = C;
            }
        }

        push(v);

        int tm = (tl + tr) >> 1;
        increase(v << 1, tl, tm, l, r, x);
        increase(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);
    }

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

            if (tl == tr){
                t[v].min = t[v].max = 0;
                t[v].add = 0;
                return;
            }

            if (t[v].max < 0){
                t[v].add += -t[v].max;
                t[v].min += -t[v].max;
                t[v].max = 0;
            }
        }

        push(v);

        int tm = (tl + tr) >> 1;
        decrease(v << 1, tl, tm, l, r, x);
        decrease(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);
    }

    void update(int l, int r, int x){
        if (x > 0) increase(1, 0, size - 1, l, r, x);
        if (x < 0) decrease(1, 0, size - 1, l, r, -x);
    }

    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);
        }
    }

    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 0 ms 212 KB Output is correct
2 Incorrect 0 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 Execution timed out 5070 ms 25316 KB Time limit exceeded
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 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -