oj.uz

답안 #815650

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
815650 2023-08-08T17:44:39 Z t6twotwo 사탕 분배 (IOI21_candies) C++17
38 / 100
 5000 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, -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[min(r, N) - 1]];
            } else if (v == 1) {
                st[p] = C[ord[min(r, N) - 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;
            push(p, l, r);
            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);
        }
        vector<int> ans(N);
        auto qry = [&](auto qry, int p, int l, int r) -> void {
            if (l + 1 == r) {
                if (l < N) {
                    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);
        };
        for (int i = 0; i < Q; i++) {
            qry(qry, 1, 0, M);
            if (V[i] < 0) {
                // int f = st[1] < -V[i] ? N : find(find, 1, 0, M, -V[i], st);
                int f = 0;
                while (f < N && st[f + M] < -V[i]) {
                    f++;
                }
                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);
                int f = 0;
                while (f < N && df[f + M] < V[i]) {
                    f++;
                }
                upd(upd, 1, 0, M, 0, f, 1, 0);
                upd(upd, 1, 0, M, f, N, 2, V[i]);
            }
        }
        
        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;
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:181:14: warning: variable 'find' set but not used [-Wunused-but-set-variable]
  181 |         auto find = [&](auto find, int p, int l, int r, int v, vector<int> &s) -> int {
      |              ^~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 8804 KB Output is correct
2 Correct 77 ms 8820 KB Output is correct
3 Correct 77 ms 8808 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 165 ms 5720 KB Output is correct
3 Correct 59 ms 24340 KB Output is correct
4 Correct 446 ms 27880 KB Output is correct
5 Correct 513 ms 27884 KB Output is correct
6 Correct 733 ms 27884 KB Output is correct
7 Correct 737 ms 27832 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 Execution timed out 5067 ms 6504 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 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 87 ms 8804 KB Output is correct
7 Correct 77 ms 8820 KB Output is correct
8 Correct 77 ms 8808 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 165 ms 5720 KB Output is correct
11 Correct 59 ms 24340 KB Output is correct
12 Correct 446 ms 27880 KB Output is correct
13 Correct 513 ms 27884 KB Output is correct
14 Correct 733 ms 27884 KB Output is correct
15 Correct 737 ms 27832 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Execution timed out 5067 ms 6504 KB Time limit exceeded
19 Halted 0 ms 0 KB -