#include <bits/stdc++.h>
#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define ll long long
using namespace std;
const int N=1e5+5;
int n,q,k;
int a[N],vm[4*N];
ll v[4*N];
void Build(Tree) {
if (l==r) {
v[h]=a[l];
vm[h]=a[l];
return ;
}
Build(Left);
Build(Right);
v[h]=v[(h<<1)]+v[((h<<1)|1)];
vm[h]=max(vm[(h<<1)],vm[((h<<1)|1)]);
}
int t,id,vl;
void Up(Tree) {
if (id<l || r<id) return ;
if (l==id && r==id) {
v[h]=a[l];
vm[h]=a[l];
return ;
}
Up(Left);
Up(Right);
v[h]=v[(h<<1)]+v[((h<<1)|1)];
vm[h]=max(vm[(h<<1)],vm[((h<<1)|1)]);
}
int L,R;
void Upd(Tree) {
if (R<l || r<L) return ;
if (vm[h]==0) return ;
if (l==r) {
v[h]/=k;
vm[h]=v[h];
return ;
}
Upd(Left);
Upd(Right);
v[h]=v[(h<<1)]+v[((h<<1)|1)];
vm[h]=max(vm[(h<<1)],vm[((h<<1)|1)]);
}
ll Get(Tree) {
if (R<l || r<L) return 0;
if (L<=l && r<=R) return v[h];
return Get(Left)+Get(Right);
}
main () {
ios::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
cin>>n>>q>>k;
for (int i=1; i<=n; i++) {
cin>>a[i];
}
Build(1,1,n);
for (int i=1; i<=q; i++) {
cin>>t;
if (t==1) {
cin>>id>>vl;
a[id]=vl;
Up(1,1,n);
}
else
if (t==2) {
cin>>L>>R;
if (k==1) continue;
Upd(1,1,n);
}
else
if (t==3) {
cin>>L>>R;
cout<<Get(1,1,n)<<"\n";
}
}
}
Compilation message
sterilizing.cpp:67:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
67 | main () {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
4 ms |
364 KB |
Output is correct |
5 |
Correct |
4 ms |
492 KB |
Output is correct |
6 |
Correct |
4 ms |
492 KB |
Output is correct |
7 |
Correct |
4 ms |
492 KB |
Output is correct |
8 |
Correct |
4 ms |
492 KB |
Output is correct |
9 |
Correct |
5 ms |
492 KB |
Output is correct |
10 |
Correct |
4 ms |
492 KB |
Output is correct |
11 |
Correct |
4 ms |
492 KB |
Output is correct |
12 |
Correct |
4 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
2540 KB |
Output is correct |
2 |
Correct |
50 ms |
2412 KB |
Output is correct |
3 |
Correct |
48 ms |
4076 KB |
Output is correct |
4 |
Correct |
58 ms |
4204 KB |
Output is correct |
5 |
Correct |
81 ms |
4332 KB |
Output is correct |
6 |
Correct |
73 ms |
4332 KB |
Output is correct |
7 |
Correct |
81 ms |
4332 KB |
Output is correct |
8 |
Correct |
72 ms |
4460 KB |
Output is correct |
9 |
Correct |
67 ms |
4332 KB |
Output is correct |
10 |
Correct |
67 ms |
4332 KB |
Output is correct |
11 |
Correct |
67 ms |
4336 KB |
Output is correct |
12 |
Correct |
67 ms |
4332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
620 KB |
Output is correct |
2 |
Correct |
14 ms |
2028 KB |
Output is correct |
3 |
Correct |
19 ms |
2028 KB |
Output is correct |
4 |
Correct |
62 ms |
1260 KB |
Output is correct |
5 |
Correct |
76 ms |
4332 KB |
Output is correct |
6 |
Correct |
75 ms |
5356 KB |
Output is correct |
7 |
Correct |
66 ms |
5612 KB |
Output is correct |
8 |
Correct |
81 ms |
5356 KB |
Output is correct |
9 |
Correct |
66 ms |
5228 KB |
Output is correct |
10 |
Correct |
66 ms |
5228 KB |
Output is correct |
11 |
Correct |
66 ms |
5228 KB |
Output is correct |
12 |
Correct |
66 ms |
5228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
99 ms |
2284 KB |
Output is correct |
2 |
Correct |
106 ms |
2284 KB |
Output is correct |
3 |
Correct |
120 ms |
2284 KB |
Output is correct |
4 |
Correct |
145 ms |
1516 KB |
Output is correct |
5 |
Correct |
160 ms |
4716 KB |
Output is correct |
6 |
Correct |
195 ms |
6636 KB |
Output is correct |
7 |
Correct |
158 ms |
6724 KB |
Output is correct |
8 |
Correct |
219 ms |
6636 KB |
Output is correct |
9 |
Correct |
202 ms |
6508 KB |
Output is correct |
10 |
Correct |
239 ms |
6508 KB |
Output is correct |
11 |
Correct |
174 ms |
6508 KB |
Output is correct |
12 |
Correct |
314 ms |
6448 KB |
Output is correct |