#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node {
ll sum;
ll mi, ma;
ll n, p;
Node() {
sum = mi = ma = 0;
n = -1, p = 0;
}
Node(ll v) {
sum = mi = ma = v;
n = -1, p = 0;
}
};
struct SegTree {
vector<Node> seg;
int MAX;
SegTree(int N) {
int i;
for(i=1;i<2*N;i*=2) {}
seg.resize(i);
MAX = i;
}
Node f(Node x, Node y) {
Node c;
c.sum = x.sum + y.sum;
c.ma = max(x.ma, y.ma);
c.mi = min(x.mi, y.mi);
c.n = -1;
c.p = 0;
return c;
}
void cons() {
for(int i = MAX/2-1;i>=1;i--) {
seg[i] = f(seg[2*i], seg[2*i+1]);
}
}
void prop(int n, int ns, int ne) {
if(seg[n].n != -1) {
seg[n].ma = seg[n].mi = (seg[n].n + seg[n].p);
seg[n].sum = seg[n].ma * (ne - ns);
if(n<MAX/2) {
seg[2*n].n = seg[n].n;
seg[2*n].p = seg[n].p;
seg[2*n+1].n = seg[n].n;
seg[2*n+1].p = seg[n].p;
}
seg[n].n = -1;
seg[n].p = 0;
}
else {
seg[n].ma += seg[n].p;
seg[n].mi += seg[n].p;
seg[n].sum += seg[n].p * (ne - ns);
if(n<MAX/2) {
seg[2*n].p += seg[n].p;
seg[2*n+1].p += seg[n].p;
}
seg[n].p = 0;
}
}
void add1(int s, int e, ll d, int n, int ns, int ne) {
prop(n,ns,ne);
if(e<=ns||ne<=s) return;
if(s<=ns&&ne<=e) {
seg[n].p += d;
prop(n,ns,ne);
return;
}
int mid = ns + ne >> 1;
add1(s, e, d, 2*n, ns, mid);
add1(s, e, d, 2*n+1, mid, ne);
if(n<MAX/2) seg[n] = f(seg[2*n], seg[2*n+1]);
}
void add2(int s, int e, ll d, int n, int ns, int ne) {
prop(n,ns,ne);
if(e<=ns||ne<=s) return;
if(s<=ns&&ne<=e) {
if(seg[n].ma / d == seg[n].mi / d) {
seg[n].n = seg[n].ma / d;
prop(n,ns,ne);
return;
}// dk-1, dk -> k-1, k
else if(seg[n].mi + 1 == seg[n].ma) {
seg[n].p -= (d-1) * (seg[n].ma / d);
prop(n,ns,ne);
return;
}
}
int mid = ns + ne >> 1;
add2(s, e, d, 2*n, ns, mid);
add2(s, e, d, 2*n+1, mid, ne);
if(n<MAX/2) seg[n] = f(seg[2*n], seg[2*n+1]);
}
ll sum(int s, int e, int n, int ns, int ne) {
prop(n,ns,ne);
if(e<=ns||ne<=s) return 0;
if(s<=ns&&ne<=e) return seg[n].sum;
int mid = ns + ne >> 1;
return sum(s, e, 2*n, ns, mid) + sum(s, e, 2*n+1, mid, ne);
}
};
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, Q, K;
cin >> N >> Q >> K;
SegTree tree(N+5);
int MAX = tree.MAX;
int i, j;
for(i=0;i<N;i++) {
ll a;
cin >> a;
tree.seg[i+MAX/2] = Node(a);
}
tree.cons();
while(Q--) {
ll a, b, c;
cin >> a >> b >>c;
b--;
if(a==1) {
ll val = tree.sum(b, b+1, 1, 0, MAX/2);
tree.add1(b, b+1, c - val, 1, 0, MAX/2);
}
if(a==2) {
tree.add2(b, c, K, 1, 0, MAX/2);
}
if(a==3) {
cout << tree.sum(b, c, 1, 0, MAX/2) << '\n';
}
}
}
Compilation message
sterilizing.cpp: In member function 'void SegTree::add1(int, int, ll, int, int, int)':
sterilizing.cpp:72:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
72 | int mid = ns + ne >> 1;
| ~~~^~~~
sterilizing.cpp: In member function 'void SegTree::add2(int, int, ll, int, int, int)':
sterilizing.cpp:92:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
92 | int mid = ns + ne >> 1;
| ~~~^~~~
sterilizing.cpp: In member function 'll SegTree::sum(int, int, int, int, int)':
sterilizing.cpp:101:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
101 | int mid = ns + ne >> 1;
| ~~~^~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:113:12: warning: unused variable 'j' [-Wunused-variable]
113 | int i, j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
4 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
6 ms |
468 KB |
Output is correct |
| 5 |
Correct |
6 ms |
724 KB |
Output is correct |
| 6 |
Correct |
6 ms |
724 KB |
Output is correct |
| 7 |
Correct |
7 ms |
732 KB |
Output is correct |
| 8 |
Correct |
6 ms |
724 KB |
Output is correct |
| 9 |
Correct |
8 ms |
724 KB |
Output is correct |
| 10 |
Correct |
6 ms |
724 KB |
Output is correct |
| 11 |
Correct |
6 ms |
724 KB |
Output is correct |
| 12 |
Correct |
6 ms |
732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5056 ms |
6648 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
1348 KB |
Output is correct |
| 2 |
Correct |
19 ms |
5700 KB |
Output is correct |
| 3 |
Correct |
34 ms |
5832 KB |
Output is correct |
| 4 |
Correct |
84 ms |
4028 KB |
Output is correct |
| 5 |
Correct |
115 ms |
11980 KB |
Output is correct |
| 6 |
Correct |
139 ms |
12104 KB |
Output is correct |
| 7 |
Correct |
104 ms |
12132 KB |
Output is correct |
| 8 |
Correct |
115 ms |
11980 KB |
Output is correct |
| 9 |
Correct |
132 ms |
12004 KB |
Output is correct |
| 10 |
Correct |
103 ms |
11984 KB |
Output is correct |
| 11 |
Correct |
105 ms |
11880 KB |
Output is correct |
| 12 |
Correct |
118 ms |
11852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
196 ms |
7072 KB |
Output is correct |
| 2 |
Correct |
181 ms |
7348 KB |
Output is correct |
| 3 |
Correct |
229 ms |
6884 KB |
Output is correct |
| 4 |
Correct |
248 ms |
4812 KB |
Output is correct |
| 5 |
Correct |
265 ms |
13288 KB |
Output is correct |
| 6 |
Correct |
313 ms |
13316 KB |
Output is correct |
| 7 |
Correct |
262 ms |
13196 KB |
Output is correct |
| 8 |
Correct |
401 ms |
13336 KB |
Output is correct |
| 9 |
Correct |
353 ms |
13128 KB |
Output is correct |
| 10 |
Correct |
434 ms |
13184 KB |
Output is correct |
| 11 |
Correct |
291 ms |
13260 KB |
Output is correct |
| 12 |
Correct |
595 ms |
13388 KB |
Output is correct |
