#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;
const ll maxn = 1e5 + 16 , md = 1e9 + 7 , inf = 2e16;
ll gcd(ll a , ll b){
if(a < b) swap(a , b);
if(b == 0) return a;
return gcd(b , a % b);
}
ll tav(ll n , ll k){
ll res = 1;
while(k > 0){
if(k & 1){
res *= n; res %= md;
}
n *= n; n %= md;
k >>= 1;
}
return res;
}
ll n , q , k;
struct segtree {
ll sz = 1;
ll val[4 * maxn][30];
vector<ll> laz;
void init(ll n){
while(sz < n) sz <<= 1;
memset(val , 0 , sizeof(val));
laz.assign(sz << 1 , 0);
return;
}
void shift(ll x , ll lx , ll rx){
ll h = laz[x];
laz[x] = 0;
if(!h) return;
if(h >= 30){
for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
} else {
for(ll j = 0 ; j + h < 30 ; j++){
val[x][j] = val[x][j + h];
}
for(ll j = 30 - h ; j < 30 ; j++) val[x][j] = 0;
}
if(rx - lx == 1) return;
ll ln = (x << 1) + 1 , rn = ln + 1;
laz[ln] += h; laz[rn] += h;
return;
}
void set(ll i , ll r , ll x , ll lx , ll rx){
shift(x , lx , rx);
if(rx <= i || lx > i) return;
if(rx - lx == 1){
val[x][0] = r;
for(ll j = 1 ; j < 30 ; j++){
val[x][j] = val[x][j - 1] / k;
}
return;
}
ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
set(i , r , ln , lx , m); set(i , r , rn , m , rx);
for(ll j = 0 ; j < 30 ; j++){
val[x][j] = val[ln][j] + val[rn][j];
}
return;
}
void set(ll i , ll r){
set(i , r , 0 , 0 , sz);
return;
}
void div(ll l , ll r , ll x , ll lx , ll rx){
shift(x , lx , rx);
if(rx <= l || lx >= r) return;
if(rx <= r && lx >= l){
laz[x] = 1;
shift(x , lx , rx);
return;
}
ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
div(l , r , ln , lx , m); div(l , r , rn , m , rx);
for(ll j = 0 ; j < 30 ; j++){
val[x][j] = val[ln][j] + val[rn][j];
}
return;
}
void div(ll l , ll r){
div(l , r , 0 , 0 , sz);
return;
}
ll cal(ll l , ll r , ll x , ll lx , ll rx){
shift(x , lx , rx);
if(rx <= l || lx >= r) return 0;
if(rx <= r && lx >= l) return val[x][0];
ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
ll a = cal(l , r , ln , lx , m) , b = cal(l , r , rn , m , rx);
return a + b;
}
ll cal(ll l , ll r){
return cal(l , r , 0 , 0 , sz);
}
};
segtree st;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>q>>k;
st.init(n);
for(ll i = 0 ; i < n ; i++){
ll h;
cin>>h;
st.set(i , h);
}
for(ll e = 0 ; e < q ; e++){
ll t;
cin>>t;
if(t == 1){
ll i , r;
cin>>i>>r; i--;
st.set(i , r);
}
if(t == 2){
ll l , r;
cin>>l>>r; l--;
st.div(l , r);
}
if(t == 3){
ll l , r;
cin>>l>>r; l--;
cout<<st.cal(l , r)<<'\n';
}
}
return 0;
}
Compilation message
sterilizing.cpp: In member function 'void segtree::set(ll, ll, ll, ll, ll)':
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp: In member function 'void segtree::div(ll, ll, ll, ll, ll)':
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp: In member function 'll segtree::cal(ll, ll, ll, ll, ll)':
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
sterilizing.cpp:59:41: warning: array subscript 30 is above array bounds of 'll [30]' {aka 'long long int [30]'} [-Warray-bounds]
59 | for(ll j = 0 ; j < 30 ; j++) val[x][h] = 0;
| ~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
94148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
305 ms |
95924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
94340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
95644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
