This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)
using namespace std;
typedef long long ll;
const int N = 100002;
int n, ma[N*4], a[N], ki, q;
ll t[4*N];
ll res = 0;
void build(int k, int l, int r){
if(l==r){
ma[k] = t[k] = a[l];
return ;
}
int m = (l + r)/2;
build(k*2, l, m);
build(k*2 + 1, m + 1, r);
t[k] = t[2*k] + t[2*k + 1];
ma[k] = max(ma[2*k], ma[2*k+1]);
}
void adjust(int k, int l, int r, int i, int x){
if(l==r){
t[k] = ma[k] = x;
return ;
}
int m = (l + r)/2;
if(i <= m) adjust(k*2, l, m, i, x);
else adjust(k*2 + 1, m + 1, r, i, x);
t[k] = t[2*k] + t[2*k + 1];
ma[k] = max(ma[2*k], ma[2*k + 1]);
}
void get1(int k, int l, int r, int i, int j){
if(r < i || l > j) return ;
if(l >= i && r <= j){
res += t[k];
return ;
}
int m = (l + r)/2;
get1(k*2, l, m, i, j);
get1(k*2 + 1, m + 1, r, i, j);
}
void divide(int k, int l, int r, int i, int j){
if(r < i || l > j) return ;
if(l >= i && r <= j){
if(ma[k]==0) return ;
if(ma[k] < ki){
ma[k] = 0;
t[k] = 0;
return ;
}
if(l==r){
t[k] = ma[k] = t[k]/ki;
return ;
}
}
int m = (l + r)/2;
divide(k*2, l, m, i, j);
divide(k*2 + 1, m + 1, r, i, j);
t[k] = t[2*k] + t[2*k + 1];
ma[k] = max(ma[2*k], ma[2*k + 1]);
}
int main(){
ios_base::sync_with_stdio(0);
cin >> n >> q >> ki;
f1(i, n) cin >> a[i];
build(1, 1, n);
while(q--){
int type; cin >> type;
if(type==1){
int x, y; cin >> x >> y;
adjust(1, 1, n, x, y);
}
if(type==2){
int l, r; cin >> l >> r;
if(ki != 1) divide(1, 1, n, l, r);
}
if(type==3){
int l, r; cin >> l >> r;
res = 0;
get1(1, 1, n, l, r);
cout << res << "\n";
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |