#include <bits/stdc++.h>
#define N 100005
#define l (2*nod)
#define r ((2*nod) + 1)
#define mid ((a + b)/2)
using namespace std;
typedef long long ll;
int n, q, k;
ll max_tree[4*N][2], v[N];
void upd(int nod, int a, int b, int i, ll x)
{
if(a == b) max_tree[nod][0] = max_tree[nod][1] = x;
else
{
if(i <= mid) upd(l, a, mid, i, x);
else upd(r, mid + 1, b, i, x);
max_tree[nod][0] = max_tree[l][0] + max_tree[r][0];
max_tree[nod][1] = max(max_tree[l][1], max_tree[r][1]);
}
}
void upd2(int nod, int a, int b, int i, int j)
{
if(i > b || j < a || !max_tree[nod][1]) return;
if(a == b)
{
max_tree[nod][0] = max_tree[nod][1] = max_tree[nod][0] / k;
return;
}
upd2(l, a, mid, i, j), upd2(r, mid + 1, b, i, j);
max_tree[nod][0] = max_tree[l][0] + max_tree[r][0];
max_tree[nod][1] = max(max_tree[l][1], max_tree[r][1]);
}
ll query(int nod, int a, int b, int i, int j)
{
if(i <= a && j >= b) return max_tree[nod][0];
if(i > b || j < a) return 0;
return query(l, a, mid, i, j) + query(r, mid + 1, b, i, j);
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>q>>k;
for(int i = 1; i <= n; i++) cin>>v[i], upd(1, 1, n, i, v[i]);
for(int i = 0; i < q; i++)
{
ll op, a, b;
cin>>op>>a>>b;
if(op == 1) upd(1, 1, n, a, b);
if(op == 2 && k >= 2) upd2(1, 1, n, a, b);
if(op == 3) cout<<query(1, 1, n, a, b)<<"\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
608 KB |
Output is correct |
| 3 |
Correct |
2 ms |
608 KB |
Output is correct |
| 4 |
Correct |
6 ms |
612 KB |
Output is correct |
| 5 |
Correct |
6 ms |
672 KB |
Output is correct |
| 6 |
Correct |
5 ms |
864 KB |
Output is correct |
| 7 |
Correct |
6 ms |
864 KB |
Output is correct |
| 8 |
Correct |
6 ms |
864 KB |
Output is correct |
| 9 |
Correct |
7 ms |
964 KB |
Output is correct |
| 10 |
Correct |
5 ms |
964 KB |
Output is correct |
| 11 |
Correct |
6 ms |
964 KB |
Output is correct |
| 12 |
Correct |
6 ms |
964 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
60 ms |
3628 KB |
Output is correct |
| 2 |
Correct |
55 ms |
3628 KB |
Output is correct |
| 3 |
Correct |
53 ms |
5680 KB |
Output is correct |
| 4 |
Correct |
72 ms |
6000 KB |
Output is correct |
| 5 |
Correct |
84 ms |
6044 KB |
Output is correct |
| 6 |
Correct |
87 ms |
6060 KB |
Output is correct |
| 7 |
Correct |
94 ms |
6060 KB |
Output is correct |
| 8 |
Correct |
94 ms |
6060 KB |
Output is correct |
| 9 |
Correct |
88 ms |
6060 KB |
Output is correct |
| 10 |
Correct |
83 ms |
6060 KB |
Output is correct |
| 11 |
Correct |
74 ms |
6060 KB |
Output is correct |
| 12 |
Correct |
73 ms |
6060 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
6060 KB |
Output is correct |
| 2 |
Correct |
19 ms |
6060 KB |
Output is correct |
| 3 |
Correct |
25 ms |
6060 KB |
Output is correct |
| 4 |
Correct |
56 ms |
6060 KB |
Output is correct |
| 5 |
Correct |
79 ms |
6060 KB |
Output is correct |
| 6 |
Correct |
85 ms |
6060 KB |
Output is correct |
| 7 |
Correct |
78 ms |
6060 KB |
Output is correct |
| 8 |
Correct |
80 ms |
6060 KB |
Output is correct |
| 9 |
Correct |
76 ms |
6060 KB |
Output is correct |
| 10 |
Correct |
77 ms |
6060 KB |
Output is correct |
| 11 |
Correct |
79 ms |
6060 KB |
Output is correct |
| 12 |
Correct |
84 ms |
6060 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
110 ms |
6060 KB |
Output is correct |
| 2 |
Correct |
114 ms |
6060 KB |
Output is correct |
| 3 |
Correct |
139 ms |
6060 KB |
Output is correct |
| 4 |
Correct |
137 ms |
6060 KB |
Output is correct |
| 5 |
Correct |
176 ms |
6060 KB |
Output is correct |
| 6 |
Correct |
198 ms |
6060 KB |
Output is correct |
| 7 |
Correct |
169 ms |
6060 KB |
Output is correct |
| 8 |
Correct |
240 ms |
6060 KB |
Output is correct |
| 9 |
Correct |
217 ms |
6060 KB |
Output is correct |
| 10 |
Correct |
250 ms |
6060 KB |
Output is correct |
| 11 |
Correct |
183 ms |
6060 KB |
Output is correct |
| 12 |
Correct |
333 ms |
6060 KB |
Output is correct |
