Submission #1097454

#TimeUsernameProblemLanguageResultExecution timeMemory
1097454avighnaMeteors (POI11_met)C++17
74 / 100
695 ms53292 KiB
#include <bits/stdc++.h> class FenwickTree { public: std::vector<long long> f; int n; FenwickTree(int n) : n(n) { f.resize(n + 1); } void add(int idx, long long del) { for (int i = idx; i <= n; i += i & (-i)) { f[i] += del; } } long long query(int idx) { long long ans = 0; for (int i = idx; i >= 1; i -= i & (-i)) { ans += f[i]; } return ans; } long long query(int l, int r) { if (l > r) { return 0; } long long ans = query(r); if (l - 1 >= 1) { ans -= query(l - 1); } return ans; } }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector owned(n + 1, std::vector<int>()); for (int i = 1, x; i <= m; ++i) { std::cin >> x; owned[x].push_back(i); } std::vector<long long> p(n + 1); for (int i = 1; i <= n; ++i) { std::cin >> p[i]; } int k; std::cin >> k; struct Update { int l, r; long long a; }; std::vector<Update> upd(k); for (auto &[l, r, a] : upd) { std::cin >> l >> r >> a; } struct State { int i, l, r; }; std::vector midpoints(k + 1, std::vector<State>()); for (int i = 0; i < n; ++i) { midpoints[(k + 1) / 2].push_back({i, 1, k}); } std::vector<int> ans(n, k + 1); for (int j = 0; j < 30; ++j) { FenwickTree tree(m + 1); auto apply = [&](int l, int r, long long d) { tree.add(l, d); tree.add(r + 1, -d); }; bool changed = false; for (int i = 1; i <= k; ++i) { if (upd[i - 1].l <= upd[i - 1].r) { apply(upd[i - 1].l, upd[i - 1].r, upd[i - 1].a); } else { apply(upd[i - 1].l, m, upd[i - 1].a); apply(1, upd[i - 1].r, upd[i - 1].a); } while (!midpoints[i].empty()) { changed = true; auto [_i, l, r] = midpoints[i].back(); midpoints[i].pop_back(); if (l > r) { continue; } long long obtained = 0; for (auto &x : owned[_i + 1]) { obtained += tree.query(x); } if (obtained >= p[_i + 1]) { ans[_i] = std::min(ans[_i], i); midpoints[(l + i - 1) / 2].push_back({_i, l, i - 1}); } else { midpoints[(i + r + 1) / 2].push_back({_i, i + 1, r}); } } } if (!changed) { break; } } for (auto &i : ans) { if (i == k + 1) { std::cout << "NIE\n"; } else { std::cout << i << '\n'; } } }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...