| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 585551 |
2022-06-29T05:02:26 Z |
SeDunion |
Wall (IOI14_wall) |
C++17 |
|
866 ms |
69740 KB |
#include "wall.h"
#include<iostream>
using namespace std;
const int N = 2e6 + 123;
const int inf = 1e9 + 123;
int n;
int fl[N << 2], fr[N << 2];
void build(int l = 0, int r = n, int v = 1) {
fl[v] = 0, fr[v] = inf;
if (r - l == 1) return;
int m = (l + r) >> 1;
build(l, m, v << 1);
build(m, r, v<<1|1);
}
void make(int &al, int &ar, int bl, int br) {
if (ar < bl) {
al = bl, ar = bl;
} else if (br < al) {
al = br, ar = br;
} else {
al = max(al, bl);
ar = min(ar, br);
}
}
void push(int v, int l, int r) {
if (r - l > 1) {
make(fl[v << 1], fr[v << 1], fl[v], fr[v]);
make(fl[v<<1|1], fr[v<<1|1], fl[v], fr[v]);
fl[v] = 0, fr[v] = inf;
}
}
void upd(int L, int R, int cl, int cr, int l = 0, int r = n, int v = 1) {
push(v, l, r);
if (L <= l && r <= R) {
make(fl[v], fr[v], cl, cr);
push(v, l, r);
return;
}
if (L >= r || l >= R) return;
int m = (l + r) >> 1;
upd(L, R, cl, cr, l, m, v << 1);
upd(L, R, cl, cr, m, r, v<<1|1);
}
int a[N];
void show(int l = 0, int r = n, int v = 1) {
push(v, l, r);
if (r - l == 1) {
a[l] = fl[v];
//cout << "[" << fl[v] << ", " << fr[v] << "] ";
return;
}
int m = (l + r) >> 1;
show(l, m, v << 1);
show(m, r, v<<1|1);
}
void buildWall(int n_, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = n_;
build();
for (int i = 0 ; i < k ; ++ i) {
if (op[i] == 1) {
upd(left[i], right[i] + 1, height[i], inf);
} else {
upd(left[i], right[i] + 1, 0, height[i]);
}
}
show();
for (int i = 0 ; i < n ; ++ i) {
finalHeight[i] = a[i];
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| 4 |
Correct |
10 ms |
696 KB |
Output is correct |
| 5 |
Correct |
7 ms |
724 KB |
Output is correct |
| 6 |
Correct |
6 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
133 ms |
8216 KB |
Output is correct |
| 3 |
Correct |
178 ms |
4268 KB |
Output is correct |
| 4 |
Correct |
535 ms |
11108 KB |
Output is correct |
| 5 |
Correct |
312 ms |
12876 KB |
Output is correct |
| 6 |
Correct |
306 ms |
12864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
284 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
6 ms |
724 KB |
Output is correct |
| 5 |
Correct |
5 ms |
724 KB |
Output is correct |
| 6 |
Correct |
5 ms |
724 KB |
Output is correct |
| 7 |
Correct |
1 ms |
292 KB |
Output is correct |
| 8 |
Correct |
134 ms |
8124 KB |
Output is correct |
| 9 |
Correct |
172 ms |
4268 KB |
Output is correct |
| 10 |
Correct |
480 ms |
11168 KB |
Output is correct |
| 11 |
Correct |
303 ms |
14564 KB |
Output is correct |
| 12 |
Correct |
350 ms |
14632 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
129 ms |
11028 KB |
Output is correct |
| 15 |
Correct |
33 ms |
2052 KB |
Output is correct |
| 16 |
Correct |
708 ms |
14432 KB |
Output is correct |
| 17 |
Correct |
296 ms |
14312 KB |
Output is correct |
| 18 |
Correct |
357 ms |
13708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| 4 |
Correct |
6 ms |
724 KB |
Output is correct |
| 5 |
Correct |
5 ms |
724 KB |
Output is correct |
| 6 |
Correct |
5 ms |
724 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
121 ms |
8116 KB |
Output is correct |
| 9 |
Correct |
182 ms |
4264 KB |
Output is correct |
| 10 |
Correct |
532 ms |
11184 KB |
Output is correct |
| 11 |
Correct |
308 ms |
13844 KB |
Output is correct |
| 12 |
Correct |
319 ms |
13792 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
134 ms |
10960 KB |
Output is correct |
| 15 |
Correct |
38 ms |
2008 KB |
Output is correct |
| 16 |
Correct |
627 ms |
14288 KB |
Output is correct |
| 17 |
Correct |
307 ms |
14176 KB |
Output is correct |
| 18 |
Correct |
355 ms |
14160 KB |
Output is correct |
| 19 |
Correct |
838 ms |
69740 KB |
Output is correct |
| 20 |
Correct |
844 ms |
67164 KB |
Output is correct |
| 21 |
Correct |
849 ms |
69708 KB |
Output is correct |
| 22 |
Correct |
764 ms |
67228 KB |
Output is correct |
| 23 |
Correct |
789 ms |
67228 KB |
Output is correct |
| 24 |
Correct |
763 ms |
67104 KB |
Output is correct |
| 25 |
Correct |
866 ms |
67108 KB |
Output is correct |
| 26 |
Correct |
848 ms |
69444 KB |
Output is correct |
| 27 |
Correct |
839 ms |
69444 KB |
Output is correct |
| 28 |
Correct |
796 ms |
66864 KB |
Output is correct |
| 29 |
Correct |
842 ms |
66804 KB |
Output is correct |
| 30 |
Correct |
784 ms |
66396 KB |
Output is correct |
