Submission #815458

#TimeUsernameProblemLanguageResultExecution timeMemory
815458t6twotwoDistributing Candies (IOI21_candies)C++17
11 / 100
84 ms8908 KiB
#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(C.begin(), C.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 (C == vector(N, C[0])) { 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; } 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...