oj.uz

Submission #815500

# Submission time Handle Problem Language Result Execution time Memory
815500 2023-08-08T15:57:51 Z t6twotwo Distributing Candies (IOI21_candies) C++17
38 / 100
 719 ms 27884 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), lz(2 * M);
        vector<ll> sum(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 apply = [&](int p, int l, int r, int v, ll s) {
            if (v == 0) {
                st[p] = 0;
                df[p] = C[ord[r - M - 1]];
            } else if (v == 1) {
                st[p] = C[ord[r - M - 1]];
                df[p] = 0;
            }
            st[p] += s;
            df[p] -= s;
            if (v != -1) {
                lz[p] = v;
                sum[p] = s;
            } else {
                sum[p] += s;
            }
        };
        auto push = [&](int p, int l, int r) {
            int m = (l + r + 1) / 2;
            apply(p * 2, l, m, lz[p], sum[p]);
            apply(p * 2 + 1, m, r, lz[p], sum[p]);
            lz[p] = -1;
            sum[p] = 0;
        };
        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 <= l && r <= R) {
                if (f == 0) {
                    apply(p, l, r, 0, 0);
                } else if (f == 1) {
                    apply(p, l, r, 1, 0);
                } else {
                    apply(p, l, r, -1, v);
                }
                return;
            }
            int m = (l + r + 1) / 2;
            push(p, l, r);
            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]);
            }
        }
        auto qry = [&](auto qry, int p, int l, int r) -> void {
            if (l + 1 >= r) {
                return;
            }
            int m = (l + r + 1) / 2;
            push(p, l, r);
            qry(qry, p * 2, l, m);
            qry(qry, p * 2 + 1, m, r);
        };
        qry(qry, 1, 0, M);
        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 0 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 85 ms 8892 KB Output is correct
2 Correct 78 ms 8908 KB Output is correct
3 Correct 79 ms 8804 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 158 ms 5740 KB Output is correct
3 Correct 52 ms 24344 KB Output is correct
4 Correct 398 ms 27876 KB Output is correct
5 Correct 485 ms 27884 KB Output is correct
6 Correct 719 ms 27880 KB Output is correct
7 Correct 663 ms 27876 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 46 ms 10172 KB Execution killed with signal 11
4 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 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 85 ms 8892 KB Output is correct
7 Correct 78 ms 8908 KB Output is correct
8 Correct 79 ms 8804 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 158 ms 5740 KB Output is correct
11 Correct 52 ms 24344 KB Output is correct
12 Correct 398 ms 27876 KB Output is correct
13 Correct 485 ms 27884 KB Output is correct
14 Correct 719 ms 27880 KB Output is correct
15 Correct 663 ms 27876 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Runtime error 46 ms 10172 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -