Submission #1236782

#TimeUsernameProblemLanguageResultExecution timeMemory
1236782fauntleroySterilizing Spray (JOI15_sterilizing)C++20
15 / 100
5092 ms4680 KiB
#include <iostream> #include <cstdio> #include <vector> #include <array> #include <string> #include <algorithm> #include <numeric> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <cmath> #include <climits> #include <iomanip> #include <limits> #include <tuple> #include <stack> #include <bitset> #include <cstring> #include <sstream> #include <functional> #include <random> #define int long long using namespace std; namespace BF { void solve(int n, int q, int k) { vector<int> a(n + 1); for (int i = 1; i <= n; ++i) cin >> a[i]; while (q--) { int s, t, u; cin >> s >> t >> u; if (s == 1) a[t] = u; else if (s == 2) { for (int i = t; i <= u; ++i) a[i] = a[i] / k; } else { int s = 0; for (int i = t; i <= u; ++i) s += a[i]; cout << s << '\n'; } } } } namespace ST { int n; vector<int> a; vector<int> seg; void build(int u, int l, int r) { if (l == r) seg[u] = a[l]; else { int mid = (l + r) >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); seg[u] = seg[u << 1] + seg[u << 1 | 1]; } } void p_upd(int u, int l, int r, int idx, int val) { if (l == r) { seg[u] += val; a[idx] += val; } else { int mid = (l + r) >> 1; if (idx <= mid) p_upd(u << 1, l, mid, idx, val); else p_upd(u << 1 | 1, mid + 1, r, idx, val); seg[u] = seg[u << 1] + seg[u << 1 | 1]; } } int query(int u, int l, int r, int ql, int qr) { if (r < ql || l > qr) return 0; if (ql <= l && r <= qr) return seg[u]; int mid = (l + r) >> 1; return query(u << 1, l, mid, ql, qr) + query(u << 1 | 1, mid + 1, r, ql, qr); } void solve(int N, int q, int k) { n = N; a.resize(n); for (auto& e : a) cin >> e; seg.assign(4 * n, 0); build(1, 0, n - 1); while (q--) { int s, t, u; cin >> s >> t >> u; --t; if (s == 1) p_upd(1, 0, n - 1, t, u - a[t]); else if (s == 2) { } else { --u; int sum = query(1, 0, n - 1, t, u); cout << sum << '\n'; } } } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q, k; cin >> n >> q >> k; if (k == 1) ST::solve(n, q, k); else BF::solve(n, q, k); 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...