제출 #1233534

#제출 시각아이디문제언어결과실행 시간메모리
1233534Timosh사탕 분배 (IOI21_candies)C++20
0 / 100
265 ms34868 KiB
#include "bits/stdc++.h" #include "candies.h" using namespace std; #define ll long long struct node { ll lz, mx, mn, eq; }; vector<node> t; vector<int> C; vector<ll> ans; int n; void push(int l, int r, int i) { if (t[i].mn + t[i].lz > C[0]) t[i].eq = C[0], t[i].mn = t[i].mx = C[0]; if (t[i].mx + t[i].lz < 0) t[i].eq = 0, t[i].mn = t[i].mx = 0; if (t[i].eq != -1) t[i].lz = 0; t[i].mx += t[i].lz; t[i].mn += t[i].lz; if (l != r) { if (t[i].eq != -1) t[i * 2].eq = t[i * 2 + 1].eq = t[i].eq; t[i * 2].lz += t[i].lz; t[i * 2 + 1].lz += t[i].lz; t[i].lz = 0; } if (l == r && t[i].eq != -1) t[i].lz = t[i].eq; t[i].eq = -1; } void upd(int l, int r, int x, int tl = 0, int tr = n - 1, int i = 1) { push(tl, tr, i); if (l > tr || tl > r) return; if (l <= tl && tr <= r && ((x + t[i].mn <= C[0]) == (x + t[i].mx <= C[0]) || (x + t[i].mn < 0) == (x + t[i].mx < 0))) { t[i].lz += x; return; } int m = (tl + tr) / 2; upd(l, r, x, tl, m, i * 2); upd(l, r, x, m + 1, tr, i * 2 + 1); t[i].mx = max(t[i * 2].mx, t[i * 2 + 1].mx); t[i].mn = min(t[i * 2].mn, t[i * 2 + 1].mn); } void get(int tl = 0, int tr = n - 1, int i = 1) { int m = (tl + tr) / 2; push(tl, tr, i); if (tl == tr) ans[tl] = t[i].lz; else { get(tl, m, i * 2); get(m + 1, tr, i * 2 + 1); } } vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) { n = c.size(); C = c; t.resize(4 * n); ans.resize(n); for (int i = 0; i < n; i++) upd(i, i, 0); for (int i = 0; i < l.size(); i++) upd(l[i], r[i], v[i]); get(); vector<int> ANS(n); for (int i = 0; i < n; i++) ANS[i] = max(min(ans[i], 1ll * c[i]), 0ll); return ANS; } // int main() // { // for (auto &i : distribute_candies({2, 4, 2}, {0, 0}, {2, 2, 1}, {5, -1, 3})) // cout << i << ' '; // return 0; // }
#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...