제출 #988670

#제출 시각아이디문제언어결과실행 시간메모리
988670mannshah1211Sterilizing Spray (JOI15_sterilizing)C++17
100 / 100
151 ms7860 KiB
/** * author: tourist * created: **/ #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif class segtree { #define lc 2 * v + 1 #define rc 2 * v + 2 #define m (ll + rr) / 2 #define pul(v) tree[v] = unite(tree[lc], tree[rc]) public: struct node { int mx = 0; long long sum = 0; node() {} node(int x) : mx(x), sum(x) {} }; node unite(const node &a, const node &b) const { node res; res.mx = max(a.mx, b.mx); res.sum = a.sum + b.sum; return res; } vector<node> tree; int n; segtree(int _n) { n = 1; while (n < _n) { n <<= 1; } tree.resize(2 * n); } void modify(int p, int x, int v, int ll, int rr) { if (rr - ll == 1) { tree[v] = node(x); return; } if (p < m) { modify(p, x, lc, ll, m); } else { modify(p, x, rc, m, rr); } pul(v); } void modify(int p, int x) { modify(p, x, 0, 0, n); } void spray(int l, int r, int k, int v, int ll, int rr) { if (ll >= r || l >= rr || tree[v].mx == 0) { return; } if (rr - ll == 1) { tree[v] = node(tree[v].mx / k); return; } spray(l, r, k, lc, ll, m); spray(l, r, k, rc, m, rr); pul(v); } void spray(int l, int r, int k) { if (k == 1) { return; } spray(l, r, k, 0, 0, n); } long long sum(int l, int r, int v, int ll, int rr) { if (ll >= r || l >= rr) { return int64_t(0); } if (ll >= l && rr <= r) { return tree[v].sum; } return sum(l, r, lc, ll, m) + sum(l, r, rc, m, rr); } long long sum(int l, int r) { return sum(l, r, 0, 0, n); } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, q, k; cin >> n >> q >> k; segtree seg(n); vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; seg.modify(i, a[i]); } while (q--) { int op; cin >> op; if (op == 1) { int p, x; cin >> p >> x; --p; seg.modify(p, x); } else if (op == 2) { int l, r; cin >> l >> r; --l; --r; seg.spray(l, r + 1, k); } else { int l, r; cin >> l >> r; --l; --r; cout << seg.sum(l, r + 1) << '\n'; } } 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...