#include <bits/stdc++.h>
#define fi first
#define se second
#define pp pop_back
#define ll long long
#define pb push_back
#define ld long double
#define debug cout << "OK\n";
#define all(x) x.begin(), x.end()
#define mp make_pair
using namespace std;
const ll N = 1e6 + 200;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll pe = mod2;
const ll pe2 = 570210983;
const ld eps = 1e-6;
/*
Rucode: jaqVYNrpMj
JUDGE_ID: 295965SY
dl:160532
*/
void data() {
#ifdef NURS
freopen("main.in", "r", stdin);
freopen("main.out", "w", stdout);
#endif
}
void speed_force() {
ios_base::sync_with_stdio(0),
cin.tie(0),cout.tie(0);
}
int n, q, k, type, l, r;
ll a[N], t[N * 4], t2[N * 4];
void upd(int pos, int val, int v = 1, int tl = 1, int tr = n)
{
if (tl == tr)
{
t[v] = val;
t2[v] = val;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm)
upd(pos, val, v * 2, tl, tm);
else
upd(pos, val, v * 2 + 1, tm + 1, tr);
t[v] = max(t[v + v], t[v + v + 1]);
t2[v] = t2[v + v] + t2[v + v + 1];
}
ll get(int l, int r, int v = 1, int tl = 1, int tr = n)
{
if (l <= tl && tr <= r)
return t2[v];
if (l > tr || r < tl)
return 0;
int tm = (tl + tr) / 2;
return get(l, r, v * 2, tl, tm) + get(l, r, v * 2 + 1, tm + 1, tr);
}
void upd2(int l, int r, int v = 1, int tl = 1, int tr = n)
{
if (l > tr || r < tl || t[v] == 0)
return;
if (tl == tr)
{
t[v] = t[v] / k, t2[v] = t2[v] / k;
return;
}
int tm = (tl + tr) / 2;
upd2(l, r, v * 2, tl, tm);
upd2(l, r, v * 2 + 1, tm + 1, tr);
t[v] = max(t[v + v], t[v + v + 1]);
t2[v] = t2[v + v] + t2[v + v + 1];
}
int main()
{
data();
speed_force();
cin >> n >> q >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
upd(i, a[i]);
}
for (int i = 1; i <= q; i++)
{
cin >> type;
if (type == 1)
{
int pos, x;
cin >> pos >> x;
upd(pos, x);
}
else if (type == 2)
{
cin >> l >> r;
if (k > 1)
{
upd2(l, r);
}
}
else
{
cin >> l >> r;
cout << get(l, r) << '\n';
}
}
}
# |
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 |
492 KB |
Output is correct |
4 |
Correct |
5 ms |
492 KB |
Output is correct |
5 |
Correct |
5 ms |
492 KB |
Output is correct |
6 |
Correct |
4 ms |
492 KB |
Output is correct |
7 |
Correct |
6 ms |
492 KB |
Output is correct |
8 |
Correct |
6 ms |
492 KB |
Output is correct |
9 |
Correct |
5 ms |
492 KB |
Output is correct |
10 |
Correct |
6 ms |
492 KB |
Output is correct |
11 |
Correct |
6 ms |
620 KB |
Output is correct |
12 |
Correct |
5 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
3308 KB |
Output is correct |
2 |
Correct |
56 ms |
3052 KB |
Output is correct |
3 |
Correct |
55 ms |
5356 KB |
Output is correct |
4 |
Correct |
72 ms |
5612 KB |
Output is correct |
5 |
Correct |
86 ms |
5740 KB |
Output is correct |
6 |
Correct |
83 ms |
5740 KB |
Output is correct |
7 |
Correct |
82 ms |
5740 KB |
Output is correct |
8 |
Correct |
83 ms |
5868 KB |
Output is correct |
9 |
Correct |
88 ms |
5740 KB |
Output is correct |
10 |
Correct |
80 ms |
5740 KB |
Output is correct |
11 |
Correct |
84 ms |
5740 KB |
Output is correct |
12 |
Correct |
77 ms |
5740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
748 KB |
Output is correct |
2 |
Correct |
20 ms |
2796 KB |
Output is correct |
3 |
Correct |
27 ms |
2924 KB |
Output is correct |
4 |
Correct |
64 ms |
1644 KB |
Output is correct |
5 |
Correct |
91 ms |
5356 KB |
Output is correct |
6 |
Correct |
85 ms |
5356 KB |
Output is correct |
7 |
Correct |
81 ms |
5484 KB |
Output is correct |
8 |
Correct |
85 ms |
5316 KB |
Output is correct |
9 |
Correct |
78 ms |
5356 KB |
Output is correct |
10 |
Correct |
80 ms |
5356 KB |
Output is correct |
11 |
Correct |
79 ms |
5356 KB |
Output is correct |
12 |
Correct |
85 ms |
5356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
108 ms |
3052 KB |
Output is correct |
2 |
Correct |
119 ms |
3052 KB |
Output is correct |
3 |
Correct |
146 ms |
2924 KB |
Output is correct |
4 |
Correct |
146 ms |
1900 KB |
Output is correct |
5 |
Correct |
178 ms |
5484 KB |
Output is correct |
6 |
Correct |
203 ms |
5484 KB |
Output is correct |
7 |
Correct |
173 ms |
5740 KB |
Output is correct |
8 |
Correct |
259 ms |
5612 KB |
Output is correct |
9 |
Correct |
228 ms |
5612 KB |
Output is correct |
10 |
Correct |
264 ms |
5612 KB |
Output is correct |
11 |
Correct |
192 ms |
5612 KB |
Output is correct |
12 |
Correct |
366 ms |
5740 KB |
Output is correct |