Submission #1236805

#TimeUsernameProblemLanguageResultExecution timeMemory
1236805fauntleroySterilizing Spray (JOI15_sterilizing)C++20
0 / 100
5093 ms7740 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; int n; vector<int>a; vector<int> seg, mx; void build(int u, int l, int r) { if (l == r) seg[u] = mx[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]; mx[u] = max(mx[u << 1], mx[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; mx[u] += 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]; mx[u] = max(mx[u << 1], mx[u << 1 | 1]); } } void div(int u, int l, int r, int ql, int qr, int k) { if (r<ql || l>qr || mx[u] < k) return; if (l == r) seg[u] /= k, a[l] /= k, mx[u] = seg[u]; else { int mid = (l + r) >> 1; div(u << 1, l, mid, ql, qr, k); div(u << 1 | 1, mid + 1, r, ql, qr, k); seg[u] = seg[u << 1] + seg[u << 1 | 1]; mx[u] = max(mx[u << 1], mx[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, q, k; cin >> n >> q >> k; a.resize(n); seg.resize(4 * n); mx.resize(4 * n); for (auto& e : a) cin >> e; build(1, 0, n - 1); while (q--) { int s, t, u; cin >> s >> t >> u; if (s == 1) p_upd(1, 0, n - 1, t - 1, u - a[t - 1]); else if (s == 2) div(1, 0, n - 1, t - 1, u - 1, k); else cout << query(1, 0, n - 1, t - 1, u - 1) << '\n'; } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); 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...