| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 232332 |
2020-05-16T18:59:27 Z |
islingr |
Wall (IOI14_wall) |
C++14 |
|
700 ms |
69888 KB |
#include <iostream>
using namespace std;
const int inf = 1e9, N = 1 << 22;
int n; int mx[N], mn[N];
void change(int v, int d, int u) {
mn[v] = max(u, min(d, mn[v]));
mx[v] = min(d, max(u, mx[v]));
}
void push(int v) {
change(v << 1|0, mn[v], mx[v]);
change(v << 1|1, mn[v], mx[v]);
mx[v] = 0; mn[v] = inf;
}
int d, u, lo, hi;
void update(int v = 1, int l = 0, int r = n) {
if (hi <= l || r <= lo) return;
if (lo <= l && r <= hi) return change(v, d, u);
push(v); int m = (l + r) / 2;
update(v << 1|0, l, m);
update(v << 1|1, m, r);
}
void final(int ans[], int v = 1, int l = 0, int r = n) {
if (r - l == 1)
return void(ans[l] = min(mx[v], mn[v]));
push(v); int m = (l + r) / 2;
final(ans, v << 1|0, l, m);
final(ans, v << 1|1, m, r);
}
void buildWall(int n, int q, int op[], int l[], int r[], int h[], int ans[]) {
::n = n;
for (int i = 0; i < N; ++i) mn[i] = inf, mx[i] = 0;
for (int i = 0; i < q; ++i) {
d = inf; u = 0;
lo = l[i]; hi = r[i] + 1;
if (op[i] == 1) u = h[i]; else d = h[i];
update();
}
final(ans);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
33152 KB |
Output is correct |
| 2 |
Correct |
23 ms |
33280 KB |
Output is correct |
| 3 |
Correct |
23 ms |
33144 KB |
Output is correct |
| 4 |
Correct |
28 ms |
33408 KB |
Output is correct |
| 5 |
Correct |
26 ms |
33408 KB |
Output is correct |
| 6 |
Correct |
26 ms |
33408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
33144 KB |
Output is correct |
| 2 |
Correct |
199 ms |
46828 KB |
Output is correct |
| 3 |
Correct |
201 ms |
40316 KB |
Output is correct |
| 4 |
Correct |
502 ms |
51208 KB |
Output is correct |
| 5 |
Correct |
330 ms |
52216 KB |
Output is correct |
| 6 |
Correct |
326 ms |
50680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
33152 KB |
Output is correct |
| 2 |
Correct |
22 ms |
33280 KB |
Output is correct |
| 3 |
Correct |
24 ms |
33152 KB |
Output is correct |
| 4 |
Correct |
27 ms |
33408 KB |
Output is correct |
| 5 |
Correct |
25 ms |
33408 KB |
Output is correct |
| 6 |
Correct |
25 ms |
33408 KB |
Output is correct |
| 7 |
Correct |
21 ms |
33152 KB |
Output is correct |
| 8 |
Correct |
200 ms |
46840 KB |
Output is correct |
| 9 |
Correct |
199 ms |
40312 KB |
Output is correct |
| 10 |
Correct |
484 ms |
51196 KB |
Output is correct |
| 11 |
Correct |
339 ms |
52224 KB |
Output is correct |
| 12 |
Correct |
338 ms |
50680 KB |
Output is correct |
| 13 |
Correct |
21 ms |
33152 KB |
Output is correct |
| 14 |
Correct |
239 ms |
46840 KB |
Output is correct |
| 15 |
Correct |
75 ms |
34424 KB |
Output is correct |
| 16 |
Correct |
542 ms |
51552 KB |
Output is correct |
| 17 |
Correct |
343 ms |
50936 KB |
Output is correct |
| 18 |
Correct |
337 ms |
50940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
33152 KB |
Output is correct |
| 2 |
Correct |
24 ms |
33336 KB |
Output is correct |
| 3 |
Correct |
24 ms |
33152 KB |
Output is correct |
| 4 |
Correct |
27 ms |
33408 KB |
Output is correct |
| 5 |
Correct |
27 ms |
33408 KB |
Output is correct |
| 6 |
Correct |
27 ms |
33408 KB |
Output is correct |
| 7 |
Correct |
23 ms |
33220 KB |
Output is correct |
| 8 |
Correct |
201 ms |
46840 KB |
Output is correct |
| 9 |
Correct |
196 ms |
40312 KB |
Output is correct |
| 10 |
Correct |
507 ms |
51192 KB |
Output is correct |
| 11 |
Correct |
330 ms |
52228 KB |
Output is correct |
| 12 |
Correct |
323 ms |
50868 KB |
Output is correct |
| 13 |
Correct |
23 ms |
33152 KB |
Output is correct |
| 14 |
Correct |
203 ms |
46840 KB |
Output is correct |
| 15 |
Correct |
49 ms |
34296 KB |
Output is correct |
| 16 |
Correct |
502 ms |
51448 KB |
Output is correct |
| 17 |
Correct |
331 ms |
50808 KB |
Output is correct |
| 18 |
Correct |
337 ms |
50936 KB |
Output is correct |
| 19 |
Correct |
678 ms |
69888 KB |
Output is correct |
| 20 |
Correct |
666 ms |
67168 KB |
Output is correct |
| 21 |
Correct |
680 ms |
69756 KB |
Output is correct |
| 22 |
Correct |
670 ms |
67064 KB |
Output is correct |
| 23 |
Correct |
674 ms |
67064 KB |
Output is correct |
| 24 |
Correct |
674 ms |
67064 KB |
Output is correct |
| 25 |
Correct |
688 ms |
67124 KB |
Output is correct |
| 26 |
Correct |
673 ms |
69624 KB |
Output is correct |
| 27 |
Correct |
666 ms |
69484 KB |
Output is correct |
| 28 |
Correct |
680 ms |
67192 KB |
Output is correct |
| 29 |
Correct |
700 ms |
67064 KB |
Output is correct |
| 30 |
Correct |
680 ms |
67320 KB |
Output is correct |
