#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const ll mod = 1e9+7;
const int maxn = 1e5 + 5;
template<typename T> struct segtree {
T merge(T x, T y) {
x += y;
return x;
}
int n;
vector<ll> t;
void init(int n) {
n += 10;
this->n = n;
t.resize(n*4);
}
void upd(int v, int tl, int tr, int i, T val) {
if (tl == tr) {
t[v] = val;
} else {
int tm = (tl+tr)/2;
if (i<=tm) {
upd(2*v,tl,tm,i,val);
} else {
upd(2*v+1,tm+1,tr,i,val);
}
t[v] = merge(t[2*v], t[2*v+1]);
}
}
T qry(int v, int tl, int tr, int l, int r) {
if (l>tr || r<tl) {
return 0;
}
if (l <= tl && tr <= r) {
return t[v];
}
int tm = (tl+tr)/2;
return merge(qry(2*v,tl,tm,l,r), qry(2*v+1,tm+1,tr,l,r));
}
};
int n, q, k;
int a[maxn];
int S[maxn], T[maxn], U[maxn];
void brute(int type, int t, int u, ll& res) {
if (type==1) {
int idx = t;
int val = u;
a[idx] = val;
}
if (type==2) {
int l = t;
int r = u;
for (int i=l; i<=r; i++) {
a[i] /= k;
}
}
if (type==3) {
res = 0;
int l = t;
int r = u;
for (int i=l; i<=r; i++) {
res += a[i];
}
}
}
void solveTask1() {
for (int i=0; i<q; i++) {
int s = S[i];
int t = T[i];
int u = U[i];
ll bans=-1; brute(s,t,u,bans);
if (s==3) cout<<bans<<"\n";
}
}
// Task2 on oj.uz
void solveTask2() {
segtree<ll> tree;
tree.init(n+10);
for (int i=1; i<=n; i++) {
tree.upd(1,1,n,i,a[i]);
}
for (int i=0; i<q; i++) {
if (S[i]==1) {
tree.upd(1,1,n,T[i],U[i]);
}
if (S[i]==3) {
cout<<tree.qry(1,1,n,T[i],U[i])<<"\n";
}
}
}
//////////////////////////////////////////////////////////////////
ll t[4*maxn];
ll mark[4*maxn];
const int NONE = -1;
void push(int v, int tl, int tr) {
if (mark[v]!=NONE) {
int tm=(tl+tr)/2;
t[2*v]=1ll*(tm-tl+1)*mark[v];
t[2*v+1]=1ll*(tr-tm)*mark[v];
mark[v*2]=mark[2*v+1]=mark[v];
mark[v]=NONE;
}
}
// ll queryRange(int v, int tl, int tr, int l, int r) {
// if (l>r) return 0;
// if (l==tl && tr==r) {
// return t[v];
// }
// push(v,tl,tr);
// int tm=(tl+tr)/2;
// return queryRange(2*v,tl,tm,l,min(tm,r))
// + queryRange(2*v+1,tm+1,tr,max(tm+1,l),r);
// }
ll queryRange(int v, int tl, int tr, int l, int r) {
if (l>tr || r<tl) return 0;
if (l<=tl && tr<=r) return t[v];
push(v,tl,tr);
int tm=(tl+tr)/2;
return queryRange(2*v,tl,tm,l,r)+queryRange(2*v+1,tm+1,tr,l,r);
}
void setRange(int v, int tl, int tr, int l, int r, int val) {
if (l>tr || r<tl) return;
if (l<=tl && tr<=r) {
t[v]=1ll*(tr-tl+1)*val;
mark[v]=val;
return;
}
push(v,tl,tr);
int tm=(tl+tr)/2;
setRange(2*v,tl,tm,l,r,val);
setRange(2*v+1,tm+1,tr,l,r,val);
t[v]=t[2*v]+t[2*v+1];
}
// void setRange(int v, int tl, int tr, int l, int r, int val) {
// if (l>r) return;
// if (l==tl && tr==r) {
// t[v]=1ll*(tr-tl+1)*val;
// mark[v]=val;
// return;
// }
// push(v,tl,tr);
// int tm=(tl+tr)/2;
// setRange(2*v,tl,tm,l,min(tm,r),val);
// setRange(2*v+1,tm+1,tr,max(tm+1,l),r,val);
// t[v]=t[2*v]+t[2*v+1];
// }
//////////////////////////////////////////////////////////////////
void solveTask3() {
//cout<<"Task3"<<endl;
bool check = false;
for (int i=1; i<=n; i++) {
setRange(1,1,n,i,i,a[i]);
}
for (int i=0; i<q; i++) {
ll bans=-1;
if (check) {
brute(S[i],T[i],U[i],bans);
}
if (S[i]==1) {
setRange(1,1,n,T[i],T[i],U[i]);
}
if (S[i]==2) {
if (k>1) {
setRange(1,1,n,T[i],U[i],0);
}
}
if (S[i]==3) {
ll res = queryRange(1,1,n,T[i],U[i]);
if (check) {
cout<<res<<" "<<bans<<endl;
assert(res==bans);
}
cout<<res<<endl;
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>q>>k;
bool isTask3 = true;
for (int i=1; i<=n; i++) {
cin>>a[i];
if (!(0<=a[i] && a[i]<=1)) isTask3=false;
}
for (int i=0; i<q; i++) {
cin>>S[i]>>T[i]>>U[i];
if (S[i]==1) {
if (!(0<=U[i] && U[i]<=1)) isTask3=false;
}
}
if (k==1) {
solveTask2();
exit(0);
}
if (isTask3) {
solveTask3();
exit(0);
}
if (n<=3000 && q<=3000) {
solveTask1();
exit(0);
}
assert(false);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
512 KB |
Output is correct |
| 5 |
Correct |
7 ms |
512 KB |
Output is correct |
| 6 |
Correct |
7 ms |
512 KB |
Output is correct |
| 7 |
Correct |
7 ms |
512 KB |
Output is correct |
| 8 |
Correct |
7 ms |
512 KB |
Output is correct |
| 9 |
Correct |
7 ms |
512 KB |
Output is correct |
| 10 |
Correct |
7 ms |
512 KB |
Output is correct |
| 11 |
Correct |
7 ms |
512 KB |
Output is correct |
| 12 |
Correct |
7 ms |
544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
58 ms |
4216 KB |
Output is correct |
| 3 |
Correct |
50 ms |
5240 KB |
Output is correct |
| 4 |
Correct |
79 ms |
6392 KB |
Output is correct |
| 5 |
Correct |
78 ms |
7032 KB |
Output is correct |
| 6 |
Correct |
77 ms |
6976 KB |
Output is correct |
| 7 |
Correct |
75 ms |
7024 KB |
Output is correct |
| 8 |
Correct |
75 ms |
6904 KB |
Output is correct |
| 9 |
Correct |
74 ms |
7032 KB |
Output is correct |
| 10 |
Correct |
75 ms |
7032 KB |
Output is correct |
| 11 |
Correct |
72 ms |
7032 KB |
Output is correct |
| 12 |
Correct |
84 ms |
7032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
1656 KB |
Output is correct |
| 2 |
Correct |
38 ms |
3072 KB |
Output is correct |
| 3 |
Correct |
52 ms |
3328 KB |
Output is correct |
| 4 |
Correct |
149 ms |
3328 KB |
Output is correct |
| 5 |
Correct |
190 ms |
6656 KB |
Output is correct |
| 6 |
Correct |
192 ms |
6776 KB |
Output is correct |
| 7 |
Correct |
71 ms |
5880 KB |
Output is correct |
| 8 |
Correct |
192 ms |
6776 KB |
Output is correct |
| 9 |
Correct |
178 ms |
6776 KB |
Output is correct |
| 10 |
Correct |
178 ms |
7288 KB |
Output is correct |
| 11 |
Correct |
182 ms |
7288 KB |
Output is correct |
| 12 |
Correct |
176 ms |
7416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
3840 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
