| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 726815 |
2023-04-19T11:54:09 Z |
allin27x |
Wall (IOI14_wall) |
C++17 |
|
739 ms |
99444 KB |
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long int;
struct SGT{
int t[(int)8e6][2] = {{0, (int)2e9}};
int n;
int ofs;
SGT(int sz){
n= sz;
ofs = 1ll<<(int)(ceil(log2(n+1)));
}
void apply(int p){
if (t[p][0]>t[2*p][1]) t[2*p][0]=t[p][0],t[2*p][1]=t[p][0]; else
if (t[2*p][0]>t[p][1]) t[2*p][0]=t[p][1], t[2*p][1]=t[p][1]; else
t[2*p][0]=max(t[2*p][0],t[p][0]), t[2*p][1]=min(t[2*p][1], t[p][1]);
if (t[p][0]>t[2*p+1][1]) t[2*p+1][0]=t[p][0],t[2*p+1][1]=t[p][0]; else
if (t[2*p+1][0]>t[p][1]) t[2*p+1][0]=t[p][1], t[2*p+1][1]=t[p][1]; else
t[2*p+1][0]=max(t[2*p+1][0],t[p][0]), t[2*p+1][1]=min(t[2*p+1][1], t[p][1]);
t[p][0] = 0; t[p][1] = (int)2e9;
}
void update(int p, int tl, int tr, int l ,int r, int h, int o){
if (p<ofs) apply(p);
if (l>r) return;
if (tl==l && tr==r){
if (o==0){
t[p][0] = max(t[p][0], h); t[p][1] = max(t[p][1], t[p][0]);
} else {
t[p][1] = min(t[p][1], h); t[p][0] = min(t[p][0], t[p][1]);
}
return;
}
int tm = (tl+tr)>>1;
update(2*p, tl, tm, l, min(tm, r), h, o);
update(2*p+1, tm+1, tr, max(l,tm+1), r, h, o);
}
void update(int l, int r, int h, int o){
update(1, 0, ofs-1, l, r, h, o);
}
void push(){
for (int i=1; i<ofs; i++){
apply(i);
}
}
};
void buildWall(int n, int k, int op[], int l[],int r[],int h[], int ans[]){
SGT st(n);
for (int i=0; i<k; i++){
st.update(l[i], r[i], h[i], op[i]-1);
}
st.push();
for (int i=0; i<n; i++) ans[i] = min(st.t[i+st.ofs][0], st.t[i+st.ofs][1]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
62836 KB |
Output is correct |
| 2 |
Correct |
35 ms |
62980 KB |
Output is correct |
| 3 |
Correct |
41 ms |
62936 KB |
Output is correct |
| 4 |
Correct |
45 ms |
63128 KB |
Output is correct |
| 5 |
Correct |
42 ms |
63096 KB |
Output is correct |
| 6 |
Correct |
44 ms |
63052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
62900 KB |
Output is correct |
| 2 |
Correct |
191 ms |
71156 KB |
Output is correct |
| 3 |
Correct |
201 ms |
66744 KB |
Output is correct |
| 4 |
Correct |
529 ms |
71760 KB |
Output is correct |
| 5 |
Correct |
379 ms |
72256 KB |
Output is correct |
| 6 |
Correct |
361 ms |
72228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
62908 KB |
Output is correct |
| 2 |
Correct |
37 ms |
62992 KB |
Output is correct |
| 3 |
Correct |
39 ms |
62956 KB |
Output is correct |
| 4 |
Correct |
44 ms |
63072 KB |
Output is correct |
| 5 |
Correct |
41 ms |
63112 KB |
Output is correct |
| 6 |
Correct |
40 ms |
63100 KB |
Output is correct |
| 7 |
Correct |
34 ms |
62884 KB |
Output is correct |
| 8 |
Correct |
183 ms |
71016 KB |
Output is correct |
| 9 |
Correct |
211 ms |
66588 KB |
Output is correct |
| 10 |
Correct |
523 ms |
71688 KB |
Output is correct |
| 11 |
Correct |
359 ms |
72236 KB |
Output is correct |
| 12 |
Correct |
341 ms |
72144 KB |
Output is correct |
| 13 |
Correct |
38 ms |
62804 KB |
Output is correct |
| 14 |
Correct |
181 ms |
71172 KB |
Output is correct |
| 15 |
Correct |
75 ms |
63836 KB |
Output is correct |
| 16 |
Correct |
720 ms |
71964 KB |
Output is correct |
| 17 |
Correct |
399 ms |
71896 KB |
Output is correct |
| 18 |
Correct |
351 ms |
71964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
62796 KB |
Output is correct |
| 2 |
Correct |
38 ms |
62916 KB |
Output is correct |
| 3 |
Correct |
39 ms |
62896 KB |
Output is correct |
| 4 |
Correct |
42 ms |
63148 KB |
Output is correct |
| 5 |
Correct |
43 ms |
63044 KB |
Output is correct |
| 6 |
Correct |
43 ms |
63116 KB |
Output is correct |
| 7 |
Correct |
32 ms |
62804 KB |
Output is correct |
| 8 |
Correct |
169 ms |
71100 KB |
Output is correct |
| 9 |
Correct |
200 ms |
66596 KB |
Output is correct |
| 10 |
Correct |
494 ms |
71660 KB |
Output is correct |
| 11 |
Correct |
325 ms |
72236 KB |
Output is correct |
| 12 |
Correct |
323 ms |
72196 KB |
Output is correct |
| 13 |
Correct |
36 ms |
62820 KB |
Output is correct |
| 14 |
Correct |
177 ms |
71064 KB |
Output is correct |
| 15 |
Correct |
79 ms |
63932 KB |
Output is correct |
| 16 |
Correct |
685 ms |
71932 KB |
Output is correct |
| 17 |
Correct |
347 ms |
71948 KB |
Output is correct |
| 18 |
Correct |
368 ms |
71928 KB |
Output is correct |
| 19 |
Correct |
739 ms |
99228 KB |
Output is correct |
| 20 |
Correct |
659 ms |
96848 KB |
Output is correct |
| 21 |
Correct |
657 ms |
99444 KB |
Output is correct |
| 22 |
Correct |
656 ms |
96796 KB |
Output is correct |
| 23 |
Correct |
640 ms |
96796 KB |
Output is correct |
| 24 |
Correct |
655 ms |
96792 KB |
Output is correct |
| 25 |
Correct |
645 ms |
96676 KB |
Output is correct |
| 26 |
Correct |
662 ms |
99232 KB |
Output is correct |
| 27 |
Correct |
655 ms |
99308 KB |
Output is correct |
| 28 |
Correct |
647 ms |
96924 KB |
Output is correct |
| 29 |
Correct |
640 ms |
96888 KB |
Output is correct |
| 30 |
Correct |
654 ms |
96800 KB |
Output is correct |
