oj.uz

Submission #777228

# Submission time Handle Problem Language Result Execution time Memory
777228 2023-07-08T19:41:08 Z dxz05 Distributing Candies (IOI21_candies) C++17
37 / 100
 461 ms 44164 KB 
#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

struct SegmentTree{
    struct node{
        long long Min, Max; // min-max suffix
        long long lazy;
        node(): Min(0), Max(0), lazy(0) {};
        node(long long x): Min(x), Max(x), lazy(0) {};
    };

    void combine(node &par, const node &lc, const node &rc){
        par.Min = min(lc.Min, rc.Min);
        par.Max = max(lc.Max, rc.Max);
    }

    node neutral_element;

    int n;
    vector<node> tree;

    SegmentTree(int _n){
        n = _n;
        tree.assign(4 * n + 5, node());
        neutral_element.Min = (long long)1e16;
        neutral_element.Max = (long long)-1e16;
    }

    void upd(int v, long long lazy){
        tree[v].Min += lazy;
        tree[v].Max += lazy;
        tree[v].lazy += lazy;
    }

    void push(int v, int tl, int tr){
        if (tl == tr || tree[v].lazy == 0) return;
        upd(v << 1, tree[v].lazy);
        upd(v << 1 | 1, tree[v].lazy);
        tree[v].lazy = 0;
    }

    void update(int v, int tl, int tr, int l, int r, long long val){
        push(v, tl, tr);
        if (l <= tl && tr <= r){
            upd(v, val);
            return;
        }
        if (tl > r || tr < l) return;

        int tm = (tl + tr) >> 1;
        update(v << 1, tl, tm, l, r, val);
        update(v << 1 | 1, tm + 1, tr, l, r, val);
        combine(tree[v], tree[v << 1], tree[v << 1 | 1]);
    }

    void update(int l, int r, long long val){
        update(1, 0, n - 1, l, r, val);
    }

    node get(int v, int tl, int tr, int l, int r){
        push(v, tl, tr);
        if (l <= tl && tr <= r) return tree[v];
        if (tl > r || tr < l) return neutral_element;
        int tm = (tl + tr) >> 1;
        node res;
        combine(res, get(v << 1, tl, tm, l, r), get(v << 1 | 1, tm + 1, tr, l, r));
        return res;
    }

    long long get_value(int pos){
        return get(1, 0, n - 1, pos, pos).Max;
    }

    long long get_diff(int l, int r){
        node res = get(1, 0, n - 1, l, r);
        return res.Max - res.Min;
    }

    int find(int v, int tl, int tr, long long Min, long long Max, int C){
        if (tl == tr) return tl;
        int tm = (tl + tr) >> 1;

        if (max(Max, tree[v << 1 | 1].Max) - min(Min, tree[v << 1 | 1].Min) >= C){
            return find(v << 1 | 1, tm + 1, tr, Min, Max, C);
        } else {
            Min = min(Min, tree[v << 1 | 1].Min);
            Max = max(Max, tree[v << 1 | 1].Max);
            return find(v << 1, tl, tm, Min, Max, C);
        }

    }

    int find(int C){
        return find(1, 0, n - 1, (long long)1e16, (long long)-1e16, C);
    }

};

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    int n = (int)C.size(), q = (int)V.size();

    V.insert(V.begin(), (int) -2e9), L.insert(L.begin(), 0), R.insert(R.begin(), n - 1);
    V.insert(V.begin(), (int) 2e9),  L.insert(L.begin(), 0), R.insert(R.begin(), n - 1);
    q += 2;

    vector<vector<int>> opening(n), closing(n);
    for (int i = 0; i < q; i++){
        opening[L[i]].push_back(i);
        closing[R[i]].push_back(i);
    }

    vector<int> ans(n, 0);

    SegmentTree st(q);
    long long sum = 0;

    for (int i = 0; i < n; i++){
        for (int k : opening[i]){
            st.update(k, q - 1, V[k]);
            sum += V[k];
        }

        int j = st.find(C[i]);

        long long diff = st.get_diff(j, q - 1) - C[i];

        long long Y = st.get_value(j);
        if (V[j + 1] > 0){ /// full
            Y += diff;
            ans[i] = sum - Y;
        } else { /// empty
            Y -= diff;
            ans[i] = C[i] + sum - Y;
        }

        assert(0 <= ans[i] && ans[i] <= C[i]);

        for (int k : closing[i]){
            st.update(k, q - 1, -V[k]);
            sum -= V[k];
        }
    }

    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 44164 KB Output is correct
2 Correct 461 ms 43780 KB Output is correct
3 Correct 413 ms 43620 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 161 ms 27752 KB Output is correct
4 Correct 85 ms 13224 KB Output is correct
5 Correct 256 ms 38468 KB Output is correct
6 Correct 254 ms 38556 KB Output is correct
7 Correct 257 ms 38608 KB Output is correct
8 Correct 257 ms 38580 KB Output is correct
9 Correct 252 ms 38608 KB Output is correct

Subtask #5
0 / 33.0

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