oj.uz

Submission #609654

# Submission time Handle Problem Language Result Execution time Memory
609654 2022-07-27T18:53:07 Z dxz05 Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 32440 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 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;
                }
            } else {
                if (t[v].min + x >= 0) {
                    t[v].min += x;
                    t[v].max += x;
                    t[v].add += x;
                    return;
                }
            }
            if (tl == tr){
                t[v].max += x;
                if (t[v].max > C) t[v].max = C;
                if (t[v].max < 0) t[v].max = 0;
                t[v].min = t[v].max;
                t[v].add = 0;
                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 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 5080 ms 25276 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 127 ms 5696 KB Output is correct
3 Correct 111 ms 21876 KB Output is correct
4 Correct 751 ms 26644 KB Output is correct
5 Correct 1772 ms 32440 KB Output is correct
6 Execution timed out 5083 ms 31948 KB Time limit exceeded
7 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 -