| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 260939 |
2020-08-11T08:18:07 Z |
my99n |
Wall (IOI14_wall) |
C++14 |
|
866 ms |
69688 KB |
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000100;
struct A {
int mn, mx;
} seg[4*MAXN];
int* ans, N;
void tag (int now, int mn, int mx) {
// cerr << "tag" << now << ' ' << mn << ' ' << mx << endl;
seg[now].mn = min(mx, max(mn, seg[now].mn));
seg[now].mx = max(mn, min(mx, seg[now].mx));
}
void push (int now, int l, int r) {
if (l == r) {
ans[l] = min(seg[now].mx, max(seg[now].mn, ans[l]));
}
else {
tag(now*2, seg[now].mn, seg[now].mx);
tag(now*2+1, seg[now].mn, seg[now].mx);
}
seg[now].mn = 0;
seg[now].mx = 1e9;
}
void build (int now = 1, int l = 0, int r = N-1) {
seg[now].mn = 0;
seg[now].mx = 1e9;
if (l == r) return;
int mid = (l+r)/2;
build(now*2, l, mid);
build(now*2+1, mid+1, r);
}
void update (int a, int b, int mn, int mx, int now = 1, int l = 0, int r = N-1) {
if (r < a or l > b) return;
if (a <= l and r <= b) return tag(now, mn, mx);
push(now, l, r);
int mid = (l+r)/2;
update(a, b, mn, mx, now*2, l, mid);
update(a, b, mn, mx, now*2+1, mid+1, r);
}
void dfs (int now = 1, int l = 0, int r = N-1) {
push(now, l, r);
if (l == r) return;
int mid = (l+r)/2;
dfs(now*2, l, mid);
dfs(now*2+1, mid+1, r);
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int finalHeight[]){
ans = finalHeight;
N = n;
build();
for(int i = 0; i < k; i++) {
if(op[i] == 1) update(l[i], r[i], h[i], 1e9);
else if(op[i] == 2) update(l[i], r[i], 0, h[i]);
}
dfs();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
7 ms |
896 KB |
Output is correct |
| 5 |
Correct |
6 ms |
768 KB |
Output is correct |
| 6 |
Correct |
7 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Correct |
182 ms |
8616 KB |
Output is correct |
| 3 |
Correct |
213 ms |
4732 KB |
Output is correct |
| 4 |
Correct |
582 ms |
11256 KB |
Output is correct |
| 5 |
Correct |
351 ms |
11896 KB |
Output is correct |
| 6 |
Correct |
374 ms |
11896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
7 ms |
768 KB |
Output is correct |
| 5 |
Correct |
6 ms |
896 KB |
Output is correct |
| 6 |
Correct |
6 ms |
768 KB |
Output is correct |
| 7 |
Correct |
1 ms |
256 KB |
Output is correct |
| 8 |
Correct |
176 ms |
8696 KB |
Output is correct |
| 9 |
Correct |
198 ms |
4728 KB |
Output is correct |
| 10 |
Correct |
574 ms |
11408 KB |
Output is correct |
| 11 |
Correct |
348 ms |
12024 KB |
Output is correct |
| 12 |
Correct |
352 ms |
11768 KB |
Output is correct |
| 13 |
Correct |
0 ms |
256 KB |
Output is correct |
| 14 |
Correct |
180 ms |
8696 KB |
Output is correct |
| 15 |
Correct |
33 ms |
2040 KB |
Output is correct |
| 16 |
Correct |
590 ms |
11676 KB |
Output is correct |
| 17 |
Correct |
342 ms |
11512 KB |
Output is correct |
| 18 |
Correct |
340 ms |
11512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
8 ms |
896 KB |
Output is correct |
| 5 |
Correct |
6 ms |
768 KB |
Output is correct |
| 6 |
Correct |
6 ms |
768 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
179 ms |
8696 KB |
Output is correct |
| 9 |
Correct |
201 ms |
4728 KB |
Output is correct |
| 10 |
Correct |
587 ms |
11384 KB |
Output is correct |
| 11 |
Correct |
357 ms |
11896 KB |
Output is correct |
| 12 |
Correct |
388 ms |
11896 KB |
Output is correct |
| 13 |
Correct |
1 ms |
256 KB |
Output is correct |
| 14 |
Correct |
178 ms |
8700 KB |
Output is correct |
| 15 |
Correct |
34 ms |
2048 KB |
Output is correct |
| 16 |
Correct |
569 ms |
11640 KB |
Output is correct |
| 17 |
Correct |
361 ms |
11668 KB |
Output is correct |
| 18 |
Correct |
396 ms |
11640 KB |
Output is correct |
| 19 |
Correct |
818 ms |
59616 KB |
Output is correct |
| 20 |
Correct |
830 ms |
67064 KB |
Output is correct |
| 21 |
Correct |
821 ms |
69624 KB |
Output is correct |
| 22 |
Correct |
816 ms |
67228 KB |
Output is correct |
| 23 |
Correct |
826 ms |
67192 KB |
Output is correct |
| 24 |
Correct |
812 ms |
67320 KB |
Output is correct |
| 25 |
Correct |
818 ms |
67088 KB |
Output is correct |
| 26 |
Correct |
846 ms |
69688 KB |
Output is correct |
| 27 |
Correct |
866 ms |
69620 KB |
Output is correct |
| 28 |
Correct |
817 ms |
67064 KB |
Output is correct |
| 29 |
Correct |
807 ms |
67320 KB |
Output is correct |
| 30 |
Correct |
808 ms |
67192 KB |
Output is correct |
