#include <bits/stdc++.h>
#define ii pair <int, int>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;
#define _ << " _ " <<
using namespace std;
inline void read(int &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void read(long long &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void writeln(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar('\n');}
inline void write(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar(' ');}
const int N = 1e5 + 7;
int n, q, k;
int a[N];
struct segTree{
int tree[4 * N];
int mx[4 * N];
int leaf[N];
inline void merge(int x){
tree[x] = tree[x << 1] + tree[x << 1 | 1];
mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}
inline void Build(int x, int low, int high){
if (low == high){
tree[x] = a[low];
mx[x] = a[low];
leaf[low] = x;
}
else{
int mid = low + high >> 1;
Build(x << 1, low, mid);
Build(x << 1 | 1, mid + 1, high);
merge(x);
}
}
inline void Update(int u, int val){
int x = leaf[u];
tree[x] = mx[x] = val;
while (1){
x >>= 1;
if (!x) return;
merge(x);
}
}
inline void Divide(int x, int l, int h, int i, int j){
if (l > j || h < i) return;
if (l >= i && h <= j){
if (mx[x] == 0) return;
if (l == h){
tree[x] /= k;
mx[x] /= k;
return;
}
}
int mid = l + h >> 1;
Divide(2 * x, l, mid, i, j);
Divide(2 * x + 1, mid + 1, h, i, j);
merge(x);
}
inline long long Query(int x, int l, int h, int i, int j){
if (l > j || h < i) return 0;
if (l >= i && h <= j) return tree[x];
int mid = l + h >> 1;
return Query(x << 1, l, mid, i, j) + Query(x << 1 | 1, mid + 1, h, i, j);
}
}IT;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
read(n); read(q); read(k);
for (int i = 1; i <= n; i++)
read(a[i]);
IT.Build(1, 1, n);
for (int i = 1; i <= q; i++){
int type;
read(type);
if (type == 1){
int id, val;
read(id); read(val);
IT.Update(id, val);
}
if (type == 2){
int l, r;
read(l); read(r);
IT.Divide(1, 1, n, l, r);
}
if (type == 3){
int l, r;
read(l); read(r);
writeln(IT.Query(1, 1, n, l, r));
}
}
}
Compilation message
sterilizing.cpp: In member function 'void segTree::Build(int, int, int)':
sterilizing.cpp:37:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = low + high >> 1;
~~~~^~~~~~
sterilizing.cpp: In member function 'void segTree::Divide(int, int, int, int, int)':
sterilizing.cpp:64:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + h >> 1;
~~^~~
sterilizing.cpp: In member function 'long long int segTree::Query(int, int, int, int, int)':
sterilizing.cpp:73:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + h >> 1;
~~^~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:82:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:82:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5008 ms |
4160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
14 ms |
2040 KB |
Output is correct |
| 3 |
Correct |
19 ms |
2168 KB |
Output is correct |
| 4 |
Correct |
55 ms |
2380 KB |
Output is correct |
| 5 |
Correct |
68 ms |
4600 KB |
Output is correct |
| 6 |
Correct |
68 ms |
4604 KB |
Output is correct |
| 7 |
Execution timed out |
5010 ms |
4396 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
93 ms |
3448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
