oj.uz

Submission #815482

# Submission time Handle Problem Language Result Execution time Memory
815482 2023-08-08T15:40:16 Z t6twotwo Distributing Candies (IOI21_candies) C++17
38 / 100
 5000 ms 27880 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = 1e18;
vector<ll> mn, mn2, mx, mx2, lazy;
void apply_add(int p, ll v) {
    lazy[p] += v;
    mn[p] += v;
    mx[p] += v;
    if (mn2[p] != inf) {
        mn2[p] += v;
    }
    if (mx2[p] != -inf) {
        mx2[p] += v;
    }
}
void apply_upd(int p, ll cmn, ll cmx) {
    if (cmn == cmx) {
        mn[p] = mx[p] = cmn;
        mn2[p] = inf;
        mx2[p] = -inf;
    } else {
        if (cmn < mx[p]) {
            if (mn[p] == mx[p]) {
                mn[p] = cmn;
            }
            if (mn2[p] == mx[p]) {
                mn2[p] = cmn;
            }
            mx[p] = cmn;
        }
        if (cmx > mn[p]) {
            if (mx[p] == mn[p]) {
                mx[p] = cmx;
            }
            if (mx2[p] == mn[p]) {
                mx2[p] = cmx;
            }
            mn[p] = cmx;
        }
    }
}
void push_add(int p) {
    apply_add(p * 2, lazy[p]);
    apply_add(p * 2 + 1, lazy[p]);
    lazy[p] = 0;
}
void push_upd(int p) {
    apply_upd(p * 2, mx[p], mn[p]);
    apply_upd(p * 2 + 1, mx[p], mn[p]);
}
void pull(int p) {
    int l = p * 2;
    int r = p * 2 + 1;
    mx[p] = max(mx[l], mx[r]);
    mn[p] = min(mn[l], mn[r]);
    mx2[p] = max(mx[p] == mx[l] ? mx2[l] : mx[l], mx[p] == mx[r] ? mx2[r] : mx[r]);
    mn2[p] = min(mn[p] == mn[l] ? mn2[l] : mn[l], mn[p] == mn[r] ? mn2[r] : mn[r]);
}
void add(int p, int l, int r, int L, int R, int v) {
    if (R <= l || r <= L) {
        return;
    }
    if (L <= l && r <= R) {
        apply_add(p, v);
        return;
    }
    int m = (l + r + 1) / 2;
    push_add(p);
    push_upd(p);
    add(p * 2, l, m, L, R, v);
    add(p * 2 + 1, m, r, L, R, v);
    pull(p);
}
void upd(int p, int l, int r, int L, int R, ll v, bool f) {
    if (R <= l || r <= L || (!f && v >= mx[p]) || (f && v <= mn[p])) {
        return;
    }
    if (L <= l && r <= R && (mn[p] == mx[p] || (!f && v > mx2[p]) || (f && v < mn2[p]))) {
        if (f) {
            apply_upd(p, inf, v);
        } else {
            apply_upd(p, v, -inf);
        }
        return;
    }
    int m = (l + r + 1) / 2;
    push_add(p);
    push_upd(p);
    upd(p * 2, l, m, L, R, v, f);
    upd(p * 2 + 1, m, r, L, R, v, f);
    pull(p);
}
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    for (int &x : R) {
        x++;
    }
    int N = C.size(), Q = V.size();
    if (N <= 2000 && Q <= 2000) {
        vector<int> A(N);
        for (int i = 0; i < Q; i++) {
            for (int j = L[i]; j < R[i]; j++) {
                A[j] += V[i];
                A[j] = max(A[j], 0);
                A[j] = min(A[j], C[j]);
            }
        }
        return A;
    }
    if (*min_element(V.begin(), V.end()) > 0) {
        vector<ll> s(N + 1);
        for (int i = 0; i < Q; i++) {
            s[L[i]] += V[i];
            s[R[i]] -= V[i];
        }
        vector<int> A(N);
        for (int i = 0; i < N; i++) {
            A[i] = min((ll)C[i], s[i]);
            s[i + 1] += s[i];
        }
        return A;
    }
    int M = 2 << __lg(N - 1);
    if (L == vector(Q, 0) && R == vector(Q, N)) {
        vector<int> ord(N);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int i, int j) {
            return C[i] < C[j];
        });
        vector<int> st(2 * M), df(2 * M);
        auto pull = [&](int i) {
            st[i] = max(st[i * 2], st[i * 2 + 1]);
            df[i] = max(df[i * 2], df[i * 2 + 1]);
        };
        auto upd = [&](auto upd, int p, int l, int r, int L, int R, int f, int v) -> void {
            if (R <= l || r <= L) {
                return;
            }
            if (l + 1 == r) {
                assert(p - M == l);
                if (f == 0) {
                    st[p] = 0;
                    df[p] = C[ord[l]];
                } else if (f == 1) {
                    st[p] = C[ord[l]];
                    df[p] = 0;
                } else {
                    st[p] += v;
                    df[p] -= v;
                }
                return;
            }
            int m = (l + r + 1) / 2;
            upd(upd, p * 2, l, m, L, R, f, v);
            upd(upd, p * 2 + 1, m, r, L, R, f, v);
            pull(p);
        };
        auto find = [&](auto find, int p, int l, int r, int v, vector<int> &s) -> int {
            if (l + 1 == r) {
                return l;
            }
            int m = (l + r + 1) / 2;
            if (s[p * 2] >= v) {
                return find(find, p * 2, l, m, v, s);
            } else {
                return find(find, p * 2 + 1, m, r, v, s);
            }
        };
        for (int i = 0; i < N; i++) {
            df[i + M] = C[ord[i]];
        }
        for (int i = M - 1; i; i--) {
            pull(i);
        }
        for (int i = 0; i < Q; i++) {
            if (V[i] < 0) {
                int f = st[1] < -V[i] ? N : find(find, 1, 0, M, -V[i], st);
                upd(upd, 1, 0, M, 0, f, 0, 0);
                upd(upd, 1, 0, M, f, N, 2, V[i]);
            } else {
                int f = df[1] < V[i] ? N : find(find, 1, 0, M, V[i], df);
                upd(upd, 1, 0, M, 0, f, 1, 0);
                upd(upd, 1, 0, M, f, N, 2, V[i]);
            }
        }
        vector<int> ans(N);
        for (int i = 0; i < N; i++) {
            ans[ord[i]] = st[i + M];
        }
        return ans;
    }
    mn.resize(2 * M, 0);
    mx.resize(2 * M, 0);
    mn2.resize(2 * M, inf);
    mx2.resize(2 * M, -inf);
    lazy.resize(2 * M);
    for (int i = 0; i < Q; i++) {
        add(1, 0, M, L[i], R[i], V[i]);
        if (V[i] > 0) {
            upd(1, 0, M, L[i], R[i], C[0], 0);
        } else {
            upd(1, 0, M, L[i], R[i], 0, 1);
        }
    }
    for (int i = 1; i < M; i++) {
        push_add(i);
        push_upd(i);
    }
    vector<int> ans(N);
    for (int i = 0; i < N; i++) {
        ans[i] = mx[i + M];
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 8808 KB Output is correct
2 Correct 116 ms 8800 KB Output is correct
3 Correct 77 ms 8800 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 211 ms 5720 KB Output is correct
3 Correct 60 ms 24336 KB Output is correct
4 Correct 428 ms 27876 KB Output is correct
5 Correct 576 ms 27880 KB Output is correct
6 Correct 785 ms 27880 KB Output is correct
7 Correct 790 ms 27880 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 5029 ms 6488 KB Time limit exceeded
4 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 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 105 ms 8808 KB Output is correct
7 Correct 116 ms 8800 KB Output is correct
8 Correct 77 ms 8800 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 211 ms 5720 KB Output is correct
11 Correct 60 ms 24336 KB Output is correct
12 Correct 428 ms 27876 KB Output is correct
13 Correct 576 ms 27880 KB Output is correct
14 Correct 785 ms 27880 KB Output is correct
15 Correct 790 ms 27880 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Execution timed out 5029 ms 6488 KB Time limit exceeded
19 Halted 0 ms 0 KB -