#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; }
};
class set_t{
public:
set<int> val;
set_t(ll val = -1){ if (~val) this->val.insert(val); }
static set_t null_v() { return set_t(); }
static set_t op(const set_t& a, const set_t& b){
set_t s;
s.val = a.val;
for (int x : b.val) s.val.insert(x);
return s;
}
set_t up(const set_t& a){ return *this = a; }
void lazy_op(const set_t& a, int l){ up(a); }
set_t operator=(const set_t& a){ this->val = a.val; return *this; }
};
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>* st1;
segtree<set_t>* st2;
void Solve(){
cin >> n >> q >> m;
memset(a, -1, sizeof(a));
for (int i = 0; i < n; i++) if (a[i]) a[i] = i;
st2 = new segtree<set_t>(n, a);
memset(a, 0, sizeof(a));
for (int i = 0; i < n; i++)
cin >> a[i];
st1 = new segtree<sum_t>(n, a);
while (q--){
ri(t);
if (t == 1){
ri(i); i--; ri(x);
int y = st1->query(i, i);
st1->update(i, i, x);
if (y && !x) st2->update(i, i, -1);
if (!y && x) st2->update(i, i, i);
}
if (t == 2){
ri(l); ri(r);
l--; r--;
set<int> s = st2->query(l, r);
for (int i : s){
int x = st1->query(i, i);
st1->update(i, i, x/m);
if (!(x/m)) st2->update(i, i, -1);
}
}
if (t == 3){
ri(l); ri(r);
l--; r--;
cout << st1->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 |
17 ms |
1988 KB |
Output is correct |
| 2 |
Correct |
38 ms |
2508 KB |
Output is correct |
| 3 |
Correct |
435 ms |
3660 KB |
Output is correct |
| 4 |
Correct |
401 ms |
3420 KB |
Output is correct |
| 5 |
Correct |
1631 ms |
5320 KB |
Output is correct |
| 6 |
Correct |
1531 ms |
5320 KB |
Output is correct |
| 7 |
Correct |
1492 ms |
5188 KB |
Output is correct |
| 8 |
Correct |
1654 ms |
5188 KB |
Output is correct |
| 9 |
Correct |
1689 ms |
5220 KB |
Output is correct |
| 10 |
Correct |
1877 ms |
5212 KB |
Output is correct |
| 11 |
Correct |
1737 ms |
5256 KB |
Output is correct |
| 12 |
Correct |
1571 ms |
5216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5089 ms |
60552 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5064 ms |
8908 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5096 ms |
66248 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
