#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) __builtin_popcountll(a)
#define bithigh(a) 63-__builtin_clzll(a)
#define lg bithigh
ll highpow(ll a) { return 1LL << (ll)lg(a); }
using namespace std;
template<class T>
class segtree{
private:
int n;
vector<T> tree, lazy;
vector<bool> f;
void init(int n){
this->n = n;
if (highpow(n)^n) this->n = 2*highpow(n);
this->tree = vector<T>(2 * this->n, T());
this->lazy = vector<T>(2 * this->n, T());
this->f = vector<bool>(2 * this->n, 0);
}
T build(int s, int l, int r, auto* arr){
if (l == r) return this->tree[s] = T(arr[l]);
int m = (l + r) / 2;
T a = build(2*s, l, m, arr);
T b = build(2*s+1, m+1, r, arr);
return this->tree[s] = T::op(a, b);
}
T update(int s, int l, int r, int ul, int ur, T x){
eval_lazy(s, l, r);
if (l > ur || r < ul) return this->tree[s];
if (l >= ul && r <= ur){
this->lazy[s].up(x);
this->f[s] = 1;
eval_lazy(s, l, r);
return this->tree[s];
}
int m = (l + r) / 2;
T a = update(2*s, l, m, ul, ur, x);
T b = update(2*s+1, m+1, r, ul, ur, x);
return this->tree[s] = T::op(a, b);
}
T query(int s, int l, int r, int ql, int qr) {
eval_lazy(s, l, r);
if (l > qr || r < ql) return T::null_v();
if (l >= ql && r <= qr) return this->tree[s];
int m = (l + r) / 2;
T a = query(2*s, l, m, ql, qr);
T b = query(2*s+1, m+1, r, ql, qr);
return T::op(a, b);
}
void eval_lazy(int s, int l, int r){
if (!this->f[s]) return;
this->tree[s].lazy_op(this->lazy[s], r-l+1);
if (l^r){
this->lazy[2*s].up(this->lazy[s]);
this->f[2*s] = 1;
this->lazy[2*s+1].up(this->lazy[s]);
this->f[2*s+1] = 1;
}
this->lazy[s] = T();
this->f[s] = 0;
}
public:
segtree(int n = 0){ init(n); }
segtree(int n, auto* arr){ init(n); build(1, 0, this->n - 1, arr); }
void update(int l, int r, auto x) { update(1, 0, this->n-1, l, r, T(x)); }
auto query(int l, int r) { if (l>r) return T::null_v().val; return query(1, 0, this->n-1, l, r).val; }
void logTree() const { for (int i = 1; i < 2*this->n; i++) this->tree[i].log(); cerr << endl; }
void logLazy() const { for (int i = 1; i < 2*this->n; i++) this->lazy[i].log(); cerr << endl; }
};
class sum_t{
public:
ll val;
sum_t(ll val = 0){ this->val = val; }
static sum_t null_v(){ return sum_t(0); }
static sum_t op(const sum_t& a, const sum_t& b){ return a + b; }
// This is currently on set mode but it can be on add.
sum_t up(const sum_t& a){ return *this = a; }
void lazy_op(const sum_t& a, int l){ up(sum_t(a.val * l)); }
sum_t operator =(const sum_t& a){ this->val = a.val; return *this; }
sum_t operator +=(const sum_t& a) { this->val += a.val; return *this; }
sum_t operator -=(const sum_t& a) { this->val -= a.val; return *this; }
sum_t operator +(const sum_t& a) const { return sum_t(this->val + a.val); }
sum_t operator -(const sum_t& a) const { return sum_t(this->val - a.val); }
bool operator ==(const sum_t& a) const { return this->val == a.val; }
bool operator !=(const sum_t& a) const { return this->val != a.val; }
void Print() const { cout << this->val << sp; }
void log() const { cerr << this->val << sp; }
};
const ll LINF = 4e18;
const int mxN = 2e5+10, INF = 2e9, mod = (1 ? 1e9+7 : 998244353);
ll n, q, m, a[mxN];
segtree<sum_t>* st;
set<int> s;
void Solve(){
cin >> n >> q >> m;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
if (a[i]) s.insert(i);
st = new segtree<sum_t>(n, a);
while (q--){
ri(t);
if (t == 1){
ri(i); i--; ri(x);
if (*s.lower_bound(i) == i) s.erase(i);
st->update(i, i, x);
if (x) s.insert(i);
}
if (t == 2){
ri(l); ri(r);
l--; r--;
if (m == 1) continue;
while (l <= r){
l = *s.lower_bound(l);
if (l > r) break;
ll x = st->query(l, l);
st->update(l, l, x / m);
if (x / m == 0) s.erase(l);
l++;
}
}
if (t == 3){
ri(l); ri(r);
l--; r--;
cout << st->query(l, r) << en;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0); cerr.tie(0);
cout << setprecision(12) << fixed;
cerr << setprecision(12) << fixed;
cerr << "Started!" << endl;
int t = 1;
//cin >> t;
while (t--)
Solve();
return 0;
}
Compilation message
sterilizing.cpp: In function 'long long int highpow(long long int)':
sterilizing.cpp:26:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
26 | #define bithigh(a) 63-__builtin_clzll(a)
| ^
sterilizing.cpp:27:12: note: in expansion of macro 'bithigh'
27 | #define lg bithigh
| ^~~~~~~
sterilizing.cpp:28:38: note: in expansion of macro 'lg'
28 | ll highpow(ll a) { return 1LL << (ll)lg(a); }
| ^~
sterilizing.cpp: At global scope:
sterilizing.cpp:45:34: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
45 | T build(int s, int l, int r, auto* arr){
| ^~~~
sterilizing.cpp:92:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
92 | segtree(int n, auto* arr){ init(n); build(1, 0, this->n - 1, arr); }
| ^~~~
sterilizing.cpp:94:31: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
94 | void update(int l, int r, auto x) { update(1, 0, this->n-1, l, r, T(x)); }
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
6 ms |
468 KB |
Output is correct |
| 4 |
Correct |
20 ms |
524 KB |
Output is correct |
| 5 |
Correct |
22 ms |
692 KB |
Output is correct |
| 6 |
Correct |
15 ms |
700 KB |
Output is correct |
| 7 |
Correct |
20 ms |
660 KB |
Output is correct |
| 8 |
Correct |
18 ms |
684 KB |
Output is correct |
| 9 |
Correct |
33 ms |
724 KB |
Output is correct |
| 10 |
Correct |
25 ms |
688 KB |
Output is correct |
| 11 |
Correct |
21 ms |
700 KB |
Output is correct |
| 12 |
Correct |
19 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
7444 KB |
Output is correct |
| 2 |
Correct |
63 ms |
6188 KB |
Output is correct |
| 3 |
Correct |
69 ms |
10572 KB |
Output is correct |
| 4 |
Correct |
90 ms |
12268 KB |
Output is correct |
| 5 |
Correct |
134 ms |
12876 KB |
Output is correct |
| 6 |
Correct |
107 ms |
12836 KB |
Output is correct |
| 7 |
Correct |
107 ms |
12772 KB |
Output is correct |
| 8 |
Correct |
113 ms |
12880 KB |
Output is correct |
| 9 |
Correct |
112 ms |
12692 KB |
Output is correct |
| 10 |
Correct |
124 ms |
12648 KB |
Output is correct |
| 11 |
Correct |
104 ms |
12700 KB |
Output is correct |
| 12 |
Correct |
119 ms |
12776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5057 ms |
852 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
359 ms |
6892 KB |
Output is correct |
| 2 |
Execution timed out |
5054 ms |
7036 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
