//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'
int n , q , k , a[100000] , lg;
arr(31) seg[400001];
int seginf[400001][2] , laz[400001];
arr(31) frm(int e){
arr(31) res;
for(int i = 0 ; i < lg ; i++){
res[i] = e % k;;
e /= k;
}
return res;
}
void readSeg(int i){
for(int bit = 0 ; bit < lg ; bit++) seg[i][bit] = seg[i << 1][bit] + seg[(i << 1) | 1][bit];
}
void buildSeg(int l = 0 , int r = n - 1 , int i = 1){
seginf[i][0] = l , seginf[i][1] = r , laz[i] = 0;
if(l == r) seg[i] = frm(a[l]);
else{
int c = (r + l - 1) >> 1;
buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1);
readSeg(i);
}
}
void shftSeg(int i , int e){
for(int bit = e ; bit < lg ; bit++) seg[i][bit - e] = seg[i][bit];
for(int bit = lg - 1 ; bit >= lg - e ; bit--) seg[i][bit] = 0;
}
void pushSeg(int i){
if(laz[i] == 0) return;
for(int ch = (i << 1) ; ch <= ((i << 1) | 1) ; ch++){
laz[ch] += laz[i] , shftSeg(ch , laz[i]);
}
laz[i] = 0;
}
void chgSeg(int l , int i , int val){
if(seginf[i][0] == l and seginf[i][1] == l) seg[i] = frm(val);
else if(seginf[i][0] <= l and seginf[i][1] >= l){
pushSeg(i);
chgSeg(l , i << 1 , val) , chgSeg(l , (i << 1) | 1 , val);
readSeg(i);
}
}
void updSeg(int l , int r , int i){
if(seginf[i][0] >= l and seginf[i][1] <= r) shftSeg(i , 1) , laz[i]++;
else if(seginf[i][1] >= l and seginf[i][0] <= r){
pushSeg(i);
updSeg(l , r , i << 1) , updSeg(l , r , (i << 1) | 1);
readSeg(i);
}
}
ll getSeg(int l , int r , int i){
if(seginf[i][0] >= l and seginf[i][1] <= r){
ll d = 1 , res = 0;
for(int bit = 0 ; bit < lg ; bit++ , d *= k) res += (d * (1ll * seg[i][bit]));
return res;
}else if(seginf[i][1] >= l and seginf[i][0] <= r){
pushSeg(i);
return (getSeg(l , r , i << 1) + getSeg(l , r , (i << 1) | 1));
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q >> k;
for(int i = 0 ; i < n ; i++) cin >> a[i];
for(int i = int(1e9) ; i >= 1 ; i /= k) lg++;
buildSeg();
for(int i = 0 ; i < q ; i++){
int op , l , r;
cin >> op >> l >> r;
if(op == 1){
chgSeg(l - 1 , 1 , r);
}else if(op == 2){
updSeg(l - 1 , r - 1 , 1);
}else{
cout << getSeg(l - 1 , r - 1 , 1) << endl;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
6492 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5030 ms |
2396 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
8536 KB |
Output is correct |
2 |
Correct |
33 ms |
23132 KB |
Output is correct |
3 |
Correct |
45 ms |
23132 KB |
Output is correct |
4 |
Incorrect |
122 ms |
15268 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
159 ms |
23484 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |