oj.uz

답안 #815586

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
815586 2023-08-08T17:09:52 Z t6twotwo 사탕 분배 (IOI21_candies) C++17
38 / 100
 727 ms 34576 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, -1);
        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]);
            }
        }
        vector<int> ans(N);
        auto qry = [&](auto qry, int p, int l, int r) -> void {
            if (l + 1 == r) {
                ans[ord[l]] = st[p];
                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);
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 13748 KB Output is correct
2 Correct 79 ms 12980 KB Output is correct
3 Correct 86 ms 12840 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 164 ms 8792 KB Output is correct
3 Correct 55 ms 26480 KB Output is correct
4 Correct 434 ms 33796 KB Output is correct
5 Correct 544 ms 34188 KB Output is correct
6 Correct 727 ms 34576 KB Output is correct
7 Correct 719 ms 33920 KB Output is correct

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Runtime error 50 ms 12732 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 83 ms 13748 KB Output is correct
7 Correct 79 ms 12980 KB Output is correct
8 Correct 86 ms 12840 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 164 ms 8792 KB Output is correct
11 Correct 55 ms 26480 KB Output is correct
12 Correct 434 ms 33796 KB Output is correct
13 Correct 544 ms 34188 KB Output is correct
14 Correct 727 ms 34576 KB Output is correct
15 Correct 719 ms 33920 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Runtime error 50 ms 12732 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -