#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
const int INF = 2e9;
const int MOD = 1e9+7;
const int MAX = 1e5+10;
const lint LNF = 2e18;
int n, q, k, A[MAX];
set<int> S;
class Seg_t{
lint T[1<<18];
void upt(int v, int s, int e, int p, int x){
if(p<s || e<p) return;
if(s==e){ T[v]=x; return; }
upt(v*2,s,(s+e)/2,p,x); upt(v*2+1,(s+e)/2+1,e,p,x);
T[v]=T[v*2]+T[v*2+1];
}
lint sum(int v, int s, int e, int l, int r){
if(e<l || r<s) return 0;
if(l<=s && e<=r) return T[v];
return sum(v*2,s,(s+e)/2,l,r) + sum(v*2+1,(s+e)/2+1,e,l,r);
}
public:
void upt(int p, int x){ upt(1,1,n,p,x); }
lint sum(int l, int r){ return sum(1,1,n,l,r); }
} Seg;
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>q>>k;
for(int i=1; i<=n; i++){
cin>>A[i]; Seg.upt(i, A[i]);
if(A[i]!=0) S.insert(i);
}
for(int i=1; i<=q; i++){
int o,x,y; cin>>o>>x>>y;
if(o==1){
A[x]=y, Seg.upt(x, A[x]);
if(A[x]!=0) S.insert(x);
}
else if(o==2){
if(k==1) continue;
auto lit=S.lower_bound(x), rit=S.upper_bound(y);
vector<int> V;
while(lit!=rit){
int p=*lit; lit++;
A[p]/=k, Seg.upt(p, A[p]);
if(A[p]==0) V.push_back(p);
}
for(int p:V) S.erase(p);
}
else if(o==3){
cout<<Seg.sum(x,y)<<'\n';
}
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
512 KB |
Output is correct |
| 4 |
Correct |
11 ms |
512 KB |
Output is correct |
| 5 |
Correct |
12 ms |
640 KB |
Output is correct |
| 6 |
Correct |
9 ms |
640 KB |
Output is correct |
| 7 |
Correct |
11 ms |
640 KB |
Output is correct |
| 8 |
Correct |
11 ms |
640 KB |
Output is correct |
| 9 |
Correct |
14 ms |
640 KB |
Output is correct |
| 10 |
Correct |
11 ms |
640 KB |
Output is correct |
| 11 |
Correct |
10 ms |
640 KB |
Output is correct |
| 12 |
Correct |
11 ms |
640 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
89 ms |
6264 KB |
Output is correct |
| 2 |
Correct |
74 ms |
5108 KB |
Output is correct |
| 3 |
Correct |
87 ms |
8312 KB |
Output is correct |
| 4 |
Correct |
129 ms |
9916 KB |
Output is correct |
| 5 |
Correct |
136 ms |
10360 KB |
Output is correct |
| 6 |
Correct |
136 ms |
10404 KB |
Output is correct |
| 7 |
Correct |
141 ms |
10488 KB |
Output is correct |
| 8 |
Correct |
139 ms |
10472 KB |
Output is correct |
| 9 |
Correct |
133 ms |
10392 KB |
Output is correct |
| 10 |
Correct |
132 ms |
10360 KB |
Output is correct |
| 11 |
Correct |
132 ms |
10360 KB |
Output is correct |
| 12 |
Correct |
133 ms |
10360 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
24 ms |
1152 KB |
Output is correct |
| 2 |
Correct |
29 ms |
2944 KB |
Output is correct |
| 3 |
Correct |
36 ms |
3168 KB |
Output is correct |
| 4 |
Correct |
64 ms |
2816 KB |
Output is correct |
| 5 |
Correct |
115 ms |
6776 KB |
Output is correct |
| 6 |
Correct |
111 ms |
6776 KB |
Output is correct |
| 7 |
Correct |
112 ms |
7160 KB |
Output is correct |
| 8 |
Correct |
110 ms |
6776 KB |
Output is correct |
| 9 |
Correct |
98 ms |
6692 KB |
Output is correct |
| 10 |
Correct |
98 ms |
6692 KB |
Output is correct |
| 11 |
Correct |
97 ms |
6564 KB |
Output is correct |
| 12 |
Correct |
100 ms |
6648 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
198 ms |
5848 KB |
Output is correct |
| 2 |
Correct |
203 ms |
5988 KB |
Output is correct |
| 3 |
Correct |
340 ms |
5112 KB |
Output is correct |
| 4 |
Correct |
211 ms |
4648 KB |
Output is correct |
| 5 |
Correct |
336 ms |
10384 KB |
Output is correct |
| 6 |
Correct |
392 ms |
10360 KB |
Output is correct |
| 7 |
Correct |
325 ms |
10232 KB |
Output is correct |
| 8 |
Correct |
525 ms |
10488 KB |
Output is correct |
| 9 |
Correct |
436 ms |
10224 KB |
Output is correct |
| 10 |
Correct |
523 ms |
10276 KB |
Output is correct |
| 11 |
Correct |
353 ms |
10340 KB |
Output is correct |
| 12 |
Correct |
725 ms |
10296 KB |
Output is correct |
