oj.uz

답안 #815466

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
815466 2023-08-08T15:27:33 Z t6twotwo 사탕 분배 (IOI21_candies) C++17
38 / 100
 5000 ms 27960 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> A(N);
        for (int i = 0; i < Q; i++) {
            if (V[i] > 0) {
                int p = 0;
                while (p < N && A[ord[p]] + V[i] >= C[ord[p]]) {
                    p++;
                }
                for (int j = 0; j < p; j++) {
                    A[ord[j]] = C[ord[j]];
                }
                for (int j = p; j < N; j++) {
                    A[ord[j]] += V[i];
                }
            } else {
                int p = 0;
                while (p < N && A[ord[p]] + V[i] <= 0) {
                    p++;
                }
                for (int j = 0; j < p; j++) {
                    A[ord[j]] = 0;
                }
                for (int j = p; j < N; j++) {
                    A[ord[j]] += V[i];
                }
            }
        }
        return A;
    }
    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 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 2 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 8808 KB Output is correct
2 Correct 76 ms 8820 KB Output is correct
3 Correct 76 ms 8800 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 154 ms 5784 KB Output is correct
3 Correct 61 ms 24356 KB Output is correct
4 Correct 436 ms 27816 KB Output is correct
5 Correct 499 ms 27960 KB Output is correct
6 Correct 767 ms 27880 KB Output is correct
7 Correct 678 ms 27880 KB Output is correct

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 370 ms 6508 KB Output is correct
4 Correct 839 ms 3496 KB Output is correct
5 Execution timed out 5042 ms 8132 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 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 2 ms 340 KB Output is correct
6 Correct 86 ms 8808 KB Output is correct
7 Correct 76 ms 8820 KB Output is correct
8 Correct 76 ms 8800 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 154 ms 5784 KB Output is correct
11 Correct 61 ms 24356 KB Output is correct
12 Correct 436 ms 27816 KB Output is correct
13 Correct 499 ms 27960 KB Output is correct
14 Correct 767 ms 27880 KB Output is correct
15 Correct 678 ms 27880 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 370 ms 6508 KB Output is correct
19 Correct 839 ms 3496 KB Output is correct
20 Execution timed out 5042 ms 8132 KB Time limit exceeded
21 Halted 0 ms 0 KB -