#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 100'010;
ll seg[N<<2];
int n, q, k;
void spray(int l, int r, int k, int i, int b, int e)
{
if (r <= b || e <= l)
return;
if (k == 1 || seg[i] == 0)
return;
if (e-b == 1) {
seg[i] /= k;
return;
}
spray(l,r,k,2*i+1,b,(b+e)/2);
spray(l,r,k,2*i+2,(b+e)/2,e);
seg[i] = seg[2*i+1] + seg[2*i+2];
}
void set_to(int p, ll x, int i, int b, int e)
{
if (e-b == 1) {
seg[i] = x;
return;
}
if (p < (b+e)/2)
set_to(p, x, 2*i+1, b, (b+e)/2);
else
set_to(p, x, 2*i+2, (b+e)/2, e);
seg[i] = seg[2*i+1] + seg[2*i+2];
}
ll get(int l, int r, int i, int b, int e)
{
if (l <= b && e <= r)
return seg[i];
if (r <= b || e <= l)
return 0;
return get(l,r,2*i+1,b,(b+e)/2) + get(l,r,2*i+2,(b+e)/2,e);
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> q >> k;
Loop (i,0,n) {
int x;
cin >> x;
set_to(i, x, 0, 0, n);
}
while (q--) {
int t, x, y;
cin >> t >> x >> y;
if (t == 1)
set_to(x-1, y, 0, 0, n);
if (t == 2)
spray(x-1, y, k, 0, 0, n);
if (t == 3)
cout << get(x-1, y, 0, 0, n) << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
3 ms |
340 KB |
Output is correct |
| 5 |
Correct |
4 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
468 KB |
Output is correct |
| 7 |
Correct |
4 ms |
468 KB |
Output is correct |
| 8 |
Correct |
3 ms |
468 KB |
Output is correct |
| 9 |
Correct |
4 ms |
472 KB |
Output is correct |
| 10 |
Correct |
3 ms |
468 KB |
Output is correct |
| 11 |
Correct |
4 ms |
428 KB |
Output is correct |
| 12 |
Correct |
3 ms |
468 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
54 ms |
3632 KB |
Output is correct |
| 2 |
Correct |
42 ms |
3304 KB |
Output is correct |
| 3 |
Correct |
41 ms |
4312 KB |
Output is correct |
| 4 |
Correct |
53 ms |
4804 KB |
Output is correct |
| 5 |
Correct |
66 ms |
5196 KB |
Output is correct |
| 6 |
Correct |
62 ms |
5232 KB |
Output is correct |
| 7 |
Correct |
63 ms |
5332 KB |
Output is correct |
| 8 |
Correct |
63 ms |
5232 KB |
Output is correct |
| 9 |
Correct |
60 ms |
5048 KB |
Output is correct |
| 10 |
Correct |
60 ms |
5048 KB |
Output is correct |
| 11 |
Correct |
60 ms |
5112 KB |
Output is correct |
| 12 |
Correct |
61 ms |
5072 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
928 KB |
Output is correct |
| 2 |
Correct |
15 ms |
1636 KB |
Output is correct |
| 3 |
Correct |
26 ms |
1748 KB |
Output is correct |
| 4 |
Correct |
46 ms |
2008 KB |
Output is correct |
| 5 |
Correct |
64 ms |
3892 KB |
Output is correct |
| 6 |
Correct |
63 ms |
3780 KB |
Output is correct |
| 7 |
Correct |
55 ms |
3900 KB |
Output is correct |
| 8 |
Correct |
64 ms |
3772 KB |
Output is correct |
| 9 |
Correct |
58 ms |
3640 KB |
Output is correct |
| 10 |
Correct |
60 ms |
3612 KB |
Output is correct |
| 11 |
Correct |
62 ms |
3684 KB |
Output is correct |
| 12 |
Correct |
58 ms |
3592 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
78 ms |
3032 KB |
Output is correct |
| 2 |
Correct |
87 ms |
3196 KB |
Output is correct |
| 3 |
Correct |
111 ms |
2576 KB |
Output is correct |
| 4 |
Correct |
116 ms |
2804 KB |
Output is correct |
| 5 |
Correct |
134 ms |
5052 KB |
Output is correct |
| 6 |
Correct |
153 ms |
5048 KB |
Output is correct |
| 7 |
Correct |
130 ms |
5036 KB |
Output is correct |
| 8 |
Correct |
180 ms |
5036 KB |
Output is correct |
| 9 |
Correct |
170 ms |
4892 KB |
Output is correct |
| 10 |
Correct |
186 ms |
4940 KB |
Output is correct |
| 11 |
Correct |
142 ms |
5120 KB |
Output is correct |
| 12 |
Correct |
249 ms |
5000 KB |
Output is correct |
