Submission #421409

#TimeUsernameProblemLanguageResultExecution timeMemory
421409tengiz05Snowball (JOI21_ho_t2)C++17
0 / 100
165 ms235132 KiB
#include <bits/stdc++.h> using i64 = long long; constexpr i64 extra = 2e16, E = 4e16, N = 1e7; struct node{ int l, r; i64 sum; bool lz; node(i64 L, i64 R) { l = r = -1; sum = R - L + 1; lz = 0; } node(){ l = r = -1; } } t[N]; int timer = 0; i64 get(i64 l, i64 r, i64 L, i64 R, int x) { if (L > r || R < l) return 0; if (t[x].lz) return 0; if (L >= l && R <= r) { i64 ans = t[x].sum; t[x].sum = 0; t[x].lz = true; return ans; } else { i64 mid = (L + R) / 2; if (t[x].l == -1) { t[x].l = timer++; t[t[x].l] = node(L, mid); } if (t[x].r == -1) { t[x].r = timer++; t[t[x].r] = node(mid + 1, R); } i64 ans = get(l, r, L, mid, t[x].l) + get(l, r, mid + 1, R, t[x].r); t[x].sum = t[t[x].l].sum + t[t[x].r].sum; return ans; } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, Q; std::cin >> n >> Q; std::vector<i64> a(n); std::vector<i64> ans(n); for (int i = 0; i < n; i++) { std::cin >> a[i]; a[i] += extra; } t[0] = node(0, E); sort(a.begin(), a.end()); while (Q--) { i64 x; std::cin >> x; if (x == 0) { continue; } else if (x > 0) { for (int i = n - 1; i >= 0; i--) { ans[i] += get(a[i], a[i] + x - 1, 0, E, 0); a[i] += x; } } else { for (int i = 0; i < n; i++) { ans[i] += get(a[i] + x, a[i] - 1, 0, E, 0); a[i] += x; } } } for (int i = 0; i < n; i++) { std::cout << ans[i] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...