제출 #482968

#제출 시각아이디문제언어결과실행 시간메모리
482968K4YANSterilizing Spray (JOI15_sterilizing)C++17
75 / 100
1127 ms102332 KiB
//Be Name Khoda #include<bits/stdc++.h> #pragma GCC optimize ("Ofast,unroll-loops") #pragma GCC target ("avx2") using namespace std; #define ll long long #define ld long double #define all(x) x.begin(), x.end() #define pii pair<int, int> #define piii pair<pii, int> #define piiii pair<pii, pii> #define piiiii pair<pii, piii> #define pll pair<ll, ll> #define plll pair<pll, ll> const ll mxn = 1e5 + 16; ll n, k, m, q, w; ll fw[mxn]; vector<int> res, g; set<int> s[3 * mxn]; struct segtree { int sz = 1; vector<ll> v; void init(ll n) { while(sz < n) sz <<= 1; v.assign(2 * sz, 0); } void add(int i, ll k, int x, int lx, int rx) { if(k > 0) { s[x].insert(i); } if(rx - lx == 1) { v[x] = k; return; } int m = (lx + rx) >> 1; if(i < m) add(i, k, 2 * x + 1, lx, m); else add(i, k, 2 * x + 2, m, rx); v[x] = v[2 * x + 1] + v[2 * x + 2]; } void add(int i, ll k) { add(i, k, 0, 0, sz); } void edit(int i, ll k, int x, int lx, int rx) { if(rx - lx == 1) { v[x] /= k; return; } int m = (lx + rx) >> 1; if(i < m) edit(i, k, 2 * x + 1, lx, m); else edit(i, k, 2 * x + 2, m, rx); v[x] = v[2 * x + 1] + v[2 * x + 2]; } void edit(int i, ll k) { edit(i, k, 0, 0, sz); } void rem(int i, int x, int lx, int rx) { s[x].erase(i); if(rx - lx == 1) { v[x] = 0; return; } int m = (lx + rx) >> 1; if(i < m) rem(i, 2 * x + 1, lx, m); else rem(i, 2 * x + 2, m, rx); v[x] = v[2 * x + 1] + v[2 * x + 2]; } void rem(int i) { rem(i, 0, 0, sz); } void cal(int l, int r, int x, int lx, int rx) { if(rx <= l || r <= lx) return; if(l <= lx && rx <= r) { for(auto it : s[x]) { res.push_back(it); } return; } int m = (lx + rx) >> 1; cal(l, r, 2 * x + 1, lx, m); cal(l, r, 2 * x + 2, m, rx); } void cal(int l, int r) { cal(l, r, 0, 0, sz); } ll ask(int l, int r, int x, int lx, int rx) { if(rx <= l || r <= lx) return 0; if(l <= lx && rx <= r) { return v[x]; } int m = (lx + rx) >> 1; ll a1 = ask(l, r, 2 * x + 1, lx, m); ll a2 = ask(l, r, 2 * x + 2, m, rx); return a1 + a2; } ll ask(int l, int r) { return ask(l, r, 0, 0, sz); } }; segtree st; void input() { cin >> n >> q >> m; for(int i = 0; i < n; i++) { cin >> w; g.push_back(w); } } void solve() { st.init(n); for(int i = 0; i < n; i++) { st.add(i, g[i]); } if(m == 1) { for(int i = 0; i < q; i++) { int si; cin >> si; if(si == 2) continue; if(si == 1) { ll a, b; cin >> a >> b; a--; g[a] = b; st.add(a, b); } if(si == 3) { int l, r; cin >> l >> r; l--; cout << st.ask(l, r) << "\n"; } } return; } for(int i = 0; i < q; i++) { int si; cin >> si; if(si == 1) { ll a, b; cin >> a >> b; a--; g[a] = b; st.rem(a); st.add(a, b); } if(si == 2) { int l, r; cin >> l >> r; l--; res.clear(); st.cal(l, r); for(auto it : res) { if(g[it] >= m) { g[it] /= m; st.edit(it, m); } else { g[it] = 0; st.rem(it); } } } if(si == 3) { int l, r; cin >> l >> r; l--; cout << st.ask(l, r) << "\n"; } } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); input(), solve(); return 0; } /* 5 10 3 1 2 8 1 3 1 2 5 2 3 5 3 2 5 2 1 4 1 3 2 3 3 5 1 2 4 2 1 2 1 1 4 3 1 5 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...