#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1.1e5;
int N, Q, K;
ll bit[MAXN];
void update(int i, int v) {
for (i++; i <= N; i += (i & -i)) {
bit[i] += v;
}
}
ll query(int i) {
ll ans = 0;
for (; i; i -= (i & -i)) {
ans += bit[i];
}
return ans;
}
map<int, int> vals;
void modify(int i, int v) {
update(i, -vals[i]);
vals.erase(i);
if (v) {
vals[i] = v;
update(i, v);
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> N >> Q >> K;
for (int i = 0; i < N; i++) {
int v; cin >> v;
modify(i, v);
}
while (Q--) {
int s, t, u; cin >> s >> t >> u;
t--;
if (s == 1) {
modify(t, u);
} else if (s == 2) {
if (K == 1) continue;
vector<pair<int, int>> cnds;
{
auto it = vals.lower_bound(t);
while (true) {
if (it == vals.end() || it->first >= u) break;
cnds.push_back(*it);
it = next(it);
}
}
for (auto it : cnds) {
modify(it.first, it.second / K);
}
} else {
cout << query(u) - query(t) << '\n';
}
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
8 ms |
504 KB |
Output is correct |
| 4 |
Correct |
23 ms |
504 KB |
Output is correct |
| 5 |
Correct |
22 ms |
504 KB |
Output is correct |
| 6 |
Correct |
15 ms |
504 KB |
Output is correct |
| 7 |
Correct |
21 ms |
644 KB |
Output is correct |
| 8 |
Correct |
20 ms |
504 KB |
Output is correct |
| 9 |
Correct |
26 ms |
504 KB |
Output is correct |
| 10 |
Correct |
19 ms |
504 KB |
Output is correct |
| 11 |
Correct |
19 ms |
632 KB |
Output is correct |
| 12 |
Correct |
20 ms |
632 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
112 ms |
4600 KB |
Output is correct |
| 2 |
Correct |
82 ms |
4184 KB |
Output is correct |
| 3 |
Correct |
109 ms |
6520 KB |
Output is correct |
| 4 |
Correct |
158 ms |
8368 KB |
Output is correct |
| 5 |
Correct |
165 ms |
8796 KB |
Output is correct |
| 6 |
Correct |
165 ms |
8796 KB |
Output is correct |
| 7 |
Correct |
166 ms |
8696 KB |
Output is correct |
| 8 |
Correct |
287 ms |
8884 KB |
Output is correct |
| 9 |
Correct |
176 ms |
8684 KB |
Output is correct |
| 10 |
Correct |
163 ms |
8568 KB |
Output is correct |
| 11 |
Correct |
160 ms |
8792 KB |
Output is correct |
| 12 |
Correct |
163 ms |
8668 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
21 ms |
632 KB |
Output is correct |
| 2 |
Correct |
32 ms |
1904 KB |
Output is correct |
| 3 |
Correct |
37 ms |
2040 KB |
Output is correct |
| 4 |
Correct |
54 ms |
1272 KB |
Output is correct |
| 5 |
Correct |
107 ms |
3704 KB |
Output is correct |
| 6 |
Correct |
111 ms |
3704 KB |
Output is correct |
| 7 |
Correct |
122 ms |
4760 KB |
Output is correct |
| 8 |
Correct |
111 ms |
4432 KB |
Output is correct |
| 9 |
Correct |
109 ms |
4496 KB |
Output is correct |
| 10 |
Correct |
149 ms |
5012 KB |
Output is correct |
| 11 |
Correct |
104 ms |
4472 KB |
Output is correct |
| 12 |
Correct |
105 ms |
4916 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
388 ms |
4000 KB |
Output is correct |
| 2 |
Correct |
373 ms |
3848 KB |
Output is correct |
| 3 |
Correct |
829 ms |
3648 KB |
Output is correct |
| 4 |
Correct |
422 ms |
2752 KB |
Output is correct |
| 5 |
Correct |
751 ms |
6780 KB |
Output is correct |
| 6 |
Correct |
999 ms |
6988 KB |
Output is correct |
| 7 |
Correct |
735 ms |
7512 KB |
Output is correct |
| 8 |
Correct |
1422 ms |
7692 KB |
Output is correct |
| 9 |
Correct |
1201 ms |
7876 KB |
Output is correct |
| 10 |
Correct |
1504 ms |
7880 KB |
Output is correct |
| 11 |
Correct |
901 ms |
7940 KB |
Output is correct |
| 12 |
Correct |
2316 ms |
7892 KB |
Output is correct |
