Submission #435099

#TimeUsernameProblemLanguageResultExecution timeMemory
435099ElegiaDistributing Candies (IOI21_candies)C++17
0 / 100
507 ms32844 KiB
#include "candies.h" #include <algorithm> #include <iostream> #include <vector> using ll = long long; const int INF = int(1e9) + 1; const int N = 1 << 18, SZ = N << 1; ll sum[SZ], minv[SZ], maxv[SZ]; void change(int o, int l, int r, int k, int v) { if (l == r) { sum[o] = v; minv[o] = std::min(v, 0); maxv[o] = std::max(v, 0); return; } int mid = (l + r) / 2; if (k <= mid) change(o << 1, l, mid, k, v); else change(o << 1 | 1, mid + 1, r, k, v); sum[o] = sum[o << 1] + sum[o << 1 | 1]; minv[o] = std::min(minv[o], sum[o << 1] + minv[o << 1 | 1]); maxv[o] = std::max(maxv[o], sum[o << 1] + maxv[o << 1 | 1]); } std::vector<std::pair<int, int>> modify[N]; std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) { int n = c.size(), m = l.size(); for (int i = 0; i != m; ++i) { modify[l[i]].emplace_back(i + 2, v[i]); modify[r[i] + 1].emplace_back(i + 2, 0); } m += 1; change(1, 0, m, 0, -INF); change(1, 0, m, 1, INF); std::vector<int> ans(n); for (int i = 0; i != n; ++i) { for (const auto& [k, v] : modify[i]) change(1, 0, m, k, v); ll vl = sum[1], vr = sum[1], s = 0; int o = 1, l = 0, r = m; while (l != r) { int mid = (l + r) / 2; ll nl = std::min(vl, sum[o << 1] + minv[o << 1 | 1]), nr = std::max(vr, sum[o << 1] + maxv[o << 1 | 1]); if (nr - nl > c[i]) { s += sum[o << 1]; o = o << 1 | 1; l = mid + 1; } else { vl = nl; vr = nr; o = o << 1; r = mid; } } if (s <= vl) ans[i] = c[i] - (vr - sum[1]); else ans[i] = sum[1] - vl; } return ans; }
#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...