| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 516714 |
2022-01-22T03:12:07 Z |
pavement |
Wall (IOI14_wall) |
C++17 |
|
743 ms |
231340 KB |
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int res[2000005];
struct node {
node *left, *right;
int S, E, lo, hi;
node(int _s, int _e) : S(_s), E(_e), lo(0), hi(100000) {
if (S == E) return;
int M = (S + E) >> 1;
left = new node(S, M);
right = new node(M + 1, E);
}
void s_upd(int v, int ty) {
if (ty == 1) {
if (v > hi) lo = hi = v;
else lo = max(lo, v);
} else {
if (v < lo) lo = hi = v;
else hi = min(hi, v);
}
}
void prop() {
if (S == E) return;
left->s_upd(lo, 1);
left->s_upd(hi, 2);
right->s_upd(lo, 1);
right->s_upd(hi, 2);
lo = 0;
hi = 100000;
}
void upd(int l, int r, int v, int ty) {
if (l > E || r < S) return;
if (l <= S && E <= r) {
s_upd(v, ty);
return;
}
prop();
left->upd(l, r, v, ty);
right->upd(l, r, v, ty);
}
void trav() {
if (S == E) {
res[S] = lo;
return;
}
prop();
left->trav();
right->trav();
}
} *root;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
root = new node(0, n - 1);
for (int i = 0; i < k; i++)
root->upd(left[i], right[i], height[i], op[i]);
root->trav();
for (int i = 0; i < n; i++) finalHeight[i] = res[i];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
3 ms |
304 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1484 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1484 KB |
Output is correct |
| 6 |
Correct |
5 ms |
1484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
300 KB |
Output is correct |
| 2 |
Correct |
136 ms |
13244 KB |
Output is correct |
| 3 |
Correct |
150 ms |
8512 KB |
Output is correct |
| 4 |
Correct |
487 ms |
26908 KB |
Output is correct |
| 5 |
Correct |
295 ms |
28600 KB |
Output is correct |
| 6 |
Correct |
248 ms |
26652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
3 ms |
396 KB |
Output is correct |
| 3 |
Correct |
3 ms |
332 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1460 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1484 KB |
Output is correct |
| 6 |
Correct |
7 ms |
1424 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
119 ms |
13232 KB |
Output is correct |
| 9 |
Correct |
160 ms |
8732 KB |
Output is correct |
| 10 |
Correct |
538 ms |
27008 KB |
Output is correct |
| 11 |
Correct |
248 ms |
28100 KB |
Output is correct |
| 12 |
Correct |
302 ms |
26424 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
130 ms |
13292 KB |
Output is correct |
| 15 |
Correct |
30 ms |
2992 KB |
Output is correct |
| 16 |
Correct |
593 ms |
27392 KB |
Output is correct |
| 17 |
Correct |
256 ms |
26928 KB |
Output is correct |
| 18 |
Correct |
258 ms |
26552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
312 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1492 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1512 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1484 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
177 ms |
13216 KB |
Output is correct |
| 9 |
Correct |
159 ms |
8872 KB |
Output is correct |
| 10 |
Correct |
534 ms |
27152 KB |
Output is correct |
| 11 |
Correct |
273 ms |
27816 KB |
Output is correct |
| 12 |
Correct |
260 ms |
26548 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
139 ms |
13208 KB |
Output is correct |
| 15 |
Correct |
30 ms |
3028 KB |
Output is correct |
| 16 |
Correct |
581 ms |
27320 KB |
Output is correct |
| 17 |
Correct |
237 ms |
26708 KB |
Output is correct |
| 18 |
Correct |
244 ms |
26684 KB |
Output is correct |
| 19 |
Correct |
732 ms |
231340 KB |
Output is correct |
| 20 |
Correct |
715 ms |
228892 KB |
Output is correct |
| 21 |
Correct |
743 ms |
231076 KB |
Output is correct |
| 22 |
Correct |
714 ms |
228456 KB |
Output is correct |
| 23 |
Correct |
724 ms |
228364 KB |
Output is correct |
| 24 |
Correct |
742 ms |
228292 KB |
Output is correct |
| 25 |
Correct |
696 ms |
227612 KB |
Output is correct |
| 26 |
Correct |
720 ms |
230288 KB |
Output is correct |
| 27 |
Correct |
695 ms |
229856 KB |
Output is correct |
| 28 |
Correct |
722 ms |
228284 KB |
Output is correct |
| 29 |
Correct |
709 ms |
228024 KB |
Output is correct |
| 30 |
Correct |
693 ms |
228452 KB |
Output is correct |
