| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 882493 |
2023-12-03T09:05:04 Z |
Desh03 |
Wall (IOI14_wall) |
C++17 |
|
733 ms |
165804 KB |
#include <bits/stdc++.h>
using namespace std;
struct node {
int mn1;
int mn2;
int mx1;
int mx2;
int mncnt;
int mxcnt;
int sum;
int lz;
node() : mn1(2e9), mn2(2e9), mx1(-2e9), mx2(-2e9), mncnt(0), mxcnt(0), sum(0), lz(0) { };
};
struct SegmentTreeBeats {
vector<node> st;
int sz;
void build(int v, int l, int r, vector<int> &a) {
if (l == r) {
st[v].mn1 = a[l];
st[v].mx1 = a[l];
st[v].mncnt = st[v].mxcnt = 1;
st[v].sum = a[l];
return;
}
int m = l + r >> 1;
build(v << 1, l, m, a);
build(v << 1 | 1, m + 1, r, a);
pull(v);
}
void applyleaf(int v, int x) {
st[v].mn1 = x;
st[v].mx1 = x;
st[v].mncnt = st[v].mxcnt = 1;
st[v].sum = x;
}
SegmentTreeBeats(vector<int> a) {
sz = a.size();
while (__builtin_popcount(sz) ^ 1) ++sz;
st.resize(sz << 1);
for (int i = 0; i < a.size(); i++) applyleaf(i + sz, a[i]);
for (int i = sz - 1; i; i--) pull(i);
}
void apply1(int v, int x, int l, int r) {
if (x == 0) return;
st[v].mx1 += x;
if (st[v].mx2 != -2e9) st[v].mx2 += x;
st[v].mn1 += x;
if (st[v].mn2 != 2e9) st[v].mn2 += x;
st[v].sum += (r - l + 1) * x;
st[v].lz += x;
}
void apply2(int v, int x, bool f) {
if (st[v].mn1 >= x) return;
st[v].sum = st[v].sum - st[v].mncnt * st[v].mn1 + st[v].mncnt * x;
if (f) {
st[v].mn1 = st[v].mx1 = x;
} else {
st[v].mn1 = x;
if (x >= st[v].mx1) st[v].mx1 = x;
else if (x > st[v].mx2) st[v].mx2 = x;
}
}
void apply3(int v, int x, bool f) {
if (st[v].mx1 <= x) return;
st[v].sum = st[v].sum - st[v].mxcnt * st[v].mx1 + st[v].mxcnt * x;
if (f) {
st[v].mx1 = st[v].mn1 = x;
} else {
st[v].mx1 = x;
if (x <= st[v].mn1) st[v].mn1 = x;
else if (x < st[v].mn2) st[v].mn2 = x;
}
}
void push(int v, int l, int r) {
int m = l + r >> 1;
apply1(v << 1, st[v].lz, l, m);
apply1(v << 1 | 1, st[v].lz, m + 1, r);
st[v].lz = 0;
apply2(v << 1, st[v].mn1, l == m);
apply2(v << 1 | 1, st[v].mn1, m + 1 == r);
apply3(v << 1, st[v].mx1, l == m);
apply3(v << 1 | 1, st[v].mx1, m + 1 == r);
}
void pull(int v) {
st[v].sum = st[v << 1].sum + st[v << 1 | 1].sum;
if (st[v << 1].mn1 == st[v << 1 | 1].mn1) {
st[v].mn1 = st[v << 1].mn1;
st[v].mncnt = st[v << 1].mncnt + st[v << 1 | 1].mncnt;
st[v].mn2 = min(st[v << 1].mn2, st[v << 1 | 1].mn2);
} else if (st[v << 1].mn1 > st[v << 1 | 1].mn1) {
st[v].mn1 = st[v << 1 | 1].mn1;
st[v].mncnt = st[v << 1 | 1].mncnt;
st[v].mn2 = min(st[v << 1].mn1, st[v << 1 | 1].mn2);
} else {
st[v].mn1 = st[v << 1].mn1;
st[v].mncnt = st[v << 1].mncnt;
st[v].mn2 = min(st[v << 1].mn2, st[v << 1 | 1].mn1);
}
if (st[v << 1].mx1 == st[v << 1 | 1].mx1) {
st[v].mx1 = st[v << 1].mx1;
st[v].mxcnt = st[v << 1].mxcnt + st[v << 1 | 1].mxcnt;
st[v].mx2 = max(st[v << 1].mx2, st[v << 1 | 1].mx2);
} else if (st[v << 1].mx1 < st[v << 1 | 1].mx1) {
st[v].mx1 = st[v << 1 | 1].mx1;
st[v].mxcnt = st[v << 1 | 1].mxcnt;
st[v].mx2 = max(st[v << 1].mx1, st[v << 1 | 1].mx2);
} else {
st[v].mx1 = st[v << 1].mx1;
st[v].mxcnt = st[v << 1].mxcnt;
st[v].mx2 = max(st[v << 1].mx2, st[v << 1 | 1].mx1);
}
}
void upd1(int v, int l, int r, int ql, int qr, int x) {
if (l > qr || r < ql) return;
if (l >= ql && r <= qr) {
apply1(v, x, l, r);
return;
}
push(v, l, r);
int m = l + r >> 1;
upd1(v << 1, l, m, ql, qr, x);
upd1(v << 1 | 1, m + 1, r, ql, qr, x);
pull(v);
}
void upd2(int v, int l, int r, int ql, int qr, int x) {
if (l > qr || r < ql || st[v].mn1 >= x) return;
if (l >= ql && r <= qr && st[v].mn2 > x) {
apply2(v, x, l == r);
return;
}
push(v, l, r);
int m = l + r >> 1;
upd2(v << 1, l, m, ql, qr, x);
upd2(v << 1 | 1, m + 1, r, ql, qr, x);
pull(v);
}
void upd3(int v, int l, int r, int ql, int qr, int x) {
if (l > qr || r < ql || st[v].mx1 <= x) return;
if (l >= ql && r <= qr && st[v].mx2 < x) {
apply3(v, x, l == r);
return;
}
push(v, l, r);
int m = l + r >> 1;
upd3(v << 1, l, m, ql, qr, x);
upd3(v << 1 | 1, m + 1, r, ql, qr, x);
pull(v);
}
void pushdown(int v, int l, int r) {
if (l == r) return;
push(v, l, r);
int m = l + r >> 1;
pushdown(v << 1, l, m);
pushdown(v << 1 | 1, m + 1, r);
}
int qry(int v, int l, int r, int ql, int qr) {
if (l > qr || r < ql) return 0;
if (l >= ql && r <= qr) return st[v].sum;
push(v, l, r);
int m = l + r >> 1;
return qry(v << 1, l, m, ql, qr) + qry(v << 1 | 1, m + 1, r, ql, qr);
}
void pushdown() {
pushdown(1, 0, sz - 1);
}
void upd1(int l, int r, int x) {
upd1(1, 0, sz - 1, l, r, x);
}
void upd2(int l, int r, int x) {
upd2(1, 0, sz - 1, l, r, x);
}
void upd3(int l, int r, int x) {
upd3(1, 0, sz - 1, l, r, x);
}
int qry(int l, int r) {
return qry(1, 0, sz - 1, l, r);
}
int get(int id) {
return st[id + sz].sum;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalheight[]) {
vector<int> a(n);
SegmentTreeBeats st(a);
for (int i = 0; i < k; i++) {
if (op[i] == 2) {
st.upd3(left[i], right[i], height[i]);
} else {
st.upd2(left[i], right[i], height[i]);
}
}
st.pushdown();
for (int i = 0; i < n; i++) {
finalheight[i] = st.get(i);
}
}
Compilation message
wall.cpp: In member function 'void SegmentTreeBeats::build(int, int, int, std::vector<int>&)':
wall.cpp:28:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
28 | int m = l + r >> 1;
| ~~^~~
wall.cpp: In constructor 'SegmentTreeBeats::SegmentTreeBeats(std::vector<int>)':
wall.cpp:43:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i = 0; i < a.size(); i++) applyleaf(i + sz, a[i]);
| ~~^~~~~~~~~~
wall.cpp: In member function 'void SegmentTreeBeats::push(int, int, int)':
wall.cpp:78:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
78 | int m = l + r >> 1;
| ~~^~~
wall.cpp: In member function 'void SegmentTreeBeats::upd1(int, int, int, int, int, int)':
wall.cpp:123:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
123 | int m = l + r >> 1;
| ~~^~~
wall.cpp: In member function 'void SegmentTreeBeats::upd2(int, int, int, int, int, int)':
wall.cpp:135:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
135 | int m = l + r >> 1;
| ~~^~~
wall.cpp: In member function 'void SegmentTreeBeats::upd3(int, int, int, int, int, int)':
wall.cpp:147:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
147 | int m = l + r >> 1;
| ~~^~~
wall.cpp: In member function 'void SegmentTreeBeats::pushdown(int, int, int)':
wall.cpp:155:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
155 | int m = l + r >> 1;
| ~~^~~
wall.cpp: In member function 'int SegmentTreeBeats::qry(int, int, int, int, int)':
wall.cpp:163:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
163 | int m = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| 3 |
Correct |
2 ms |
500 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1624 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1624 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
103 ms |
8324 KB |
Output is correct |
| 3 |
Correct |
53 ms |
5796 KB |
Output is correct |
| 4 |
Correct |
139 ms |
26868 KB |
Output is correct |
| 5 |
Correct |
142 ms |
27364 KB |
Output is correct |
| 6 |
Correct |
170 ms |
25804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1628 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1628 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1628 KB |
Output is correct |
| 7 |
Correct |
0 ms |
600 KB |
Output is correct |
| 8 |
Correct |
103 ms |
13884 KB |
Output is correct |
| 9 |
Correct |
54 ms |
9640 KB |
Output is correct |
| 10 |
Correct |
144 ms |
26836 KB |
Output is correct |
| 11 |
Correct |
139 ms |
27316 KB |
Output is correct |
| 12 |
Correct |
167 ms |
25780 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
109 ms |
13936 KB |
Output is correct |
| 15 |
Correct |
31 ms |
3692 KB |
Output is correct |
| 16 |
Correct |
512 ms |
26736 KB |
Output is correct |
| 17 |
Correct |
268 ms |
26284 KB |
Output is correct |
| 18 |
Correct |
283 ms |
26196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| 3 |
Correct |
2 ms |
344 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1628 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1628 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1724 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
103 ms |
13924 KB |
Output is correct |
| 9 |
Correct |
53 ms |
9556 KB |
Output is correct |
| 10 |
Correct |
136 ms |
27004 KB |
Output is correct |
| 11 |
Correct |
141 ms |
27336 KB |
Output is correct |
| 12 |
Correct |
173 ms |
25760 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
104 ms |
13920 KB |
Output is correct |
| 15 |
Correct |
32 ms |
3676 KB |
Output is correct |
| 16 |
Correct |
513 ms |
26820 KB |
Output is correct |
| 17 |
Correct |
268 ms |
26196 KB |
Output is correct |
| 18 |
Correct |
272 ms |
26200 KB |
Output is correct |
| 19 |
Correct |
649 ms |
165540 KB |
Output is correct |
| 20 |
Correct |
659 ms |
165540 KB |
Output is correct |
| 21 |
Correct |
633 ms |
165576 KB |
Output is correct |
| 22 |
Correct |
643 ms |
165588 KB |
Output is correct |
| 23 |
Correct |
697 ms |
165540 KB |
Output is correct |
| 24 |
Correct |
655 ms |
165804 KB |
Output is correct |
| 25 |
Correct |
733 ms |
165596 KB |
Output is correct |
| 26 |
Correct |
672 ms |
165544 KB |
Output is correct |
| 27 |
Correct |
637 ms |
165544 KB |
Output is correct |
| 28 |
Correct |
691 ms |
165692 KB |
Output is correct |
| 29 |
Correct |
623 ms |
165672 KB |
Output is correct |
| 30 |
Correct |
647 ms |
165688 KB |
Output is correct |
