| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 230790 |
2020-05-11T18:28:39 Z |
cheissmart |
Wall (IOI14_wall) |
C++14 |
|
742 ms |
62224 KB |
#include "wall.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(v) (v).beign(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
const int N = 2000006, INF = 1e9 + 7;
struct S {
int ub, lb;
} t[N * 4];
void init(int v, int tl, int tr) {
t[v].ub = INF;
t[v].lb = 0;
if(tr - tl == 1) return;
int tm = (tl + tr) / 2;
init(v*2, tl, tm);
init(v*2+1, tm, tr);
}
void put_tag(int v, int op, int h) {
if(op == 1) { // lb
t[v].lb = max(t[v].lb, h);
if(t[v].lb >= t[v].ub) t[v].ub = t[v].lb;
} else { // rb
t[v].ub = min(t[v].ub, h);
if(t[v].lb >= t[v].ub) t[v].lb = t[v].ub;
}
}
void push(int v) {
put_tag(v*2, 1, t[v].lb);
put_tag(v*2, 2, t[v].ub);
put_tag(v*2+1, 1, t[v].lb);
put_tag(v*2+1, 2, t[v].ub);
t[v].lb = 0, t[v].ub = INF;
}
void upd(int l, int r, int op, int h, int v, int tl, int tr) {
if(l >= r) return;
if(l == tl && r == tr) {
put_tag(v, op, h);
return;
}
push(v);
int tm = (tl + tr) / 2;
upd(l, min(r, tm), op, h, v*2, tl, tm);
upd(max(l, tm), r, op, h, v*2+1, tm, tr);
}
void build_ans(int v, int tl, int tr, int* ans) {
if(tr - tl == 1) {
ans[tl] = t[v].lb;
return;
}
push(v);
int tm = (tl + tr) / 2;
build_ans(v*2, tl, tm, ans);
build_ans(v*2 + 1, tm, tr, ans);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
init(1, 0, n);
for(int i = 0; i < k;i++) {
upd(left[i], right[i] + 1, op[i], height[i], 1, 0, n);
}
build_ans(1, 0, n, finalHeight);
return;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
6 ms |
512 KB |
Output is correct |
| 3 |
Correct |
6 ms |
384 KB |
Output is correct |
| 4 |
Correct |
12 ms |
896 KB |
Output is correct |
| 5 |
Correct |
10 ms |
896 KB |
Output is correct |
| 6 |
Correct |
10 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
172 ms |
11004 KB |
Output is correct |
| 3 |
Correct |
177 ms |
7032 KB |
Output is correct |
| 4 |
Correct |
473 ms |
13944 KB |
Output is correct |
| 5 |
Correct |
314 ms |
14420 KB |
Output is correct |
| 6 |
Correct |
317 ms |
14328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
6 ms |
512 KB |
Output is correct |
| 3 |
Correct |
6 ms |
384 KB |
Output is correct |
| 4 |
Correct |
11 ms |
896 KB |
Output is correct |
| 5 |
Correct |
9 ms |
896 KB |
Output is correct |
| 6 |
Correct |
9 ms |
896 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
175 ms |
11044 KB |
Output is correct |
| 9 |
Correct |
175 ms |
7032 KB |
Output is correct |
| 10 |
Correct |
482 ms |
13944 KB |
Output is correct |
| 11 |
Correct |
322 ms |
14456 KB |
Output is correct |
| 12 |
Correct |
306 ms |
14456 KB |
Output is correct |
| 13 |
Correct |
4 ms |
256 KB |
Output is correct |
| 14 |
Correct |
172 ms |
11256 KB |
Output is correct |
| 15 |
Correct |
39 ms |
2040 KB |
Output is correct |
| 16 |
Correct |
611 ms |
14300 KB |
Output is correct |
| 17 |
Correct |
317 ms |
14076 KB |
Output is correct |
| 18 |
Correct |
324 ms |
14200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
6 ms |
512 KB |
Output is correct |
| 3 |
Correct |
6 ms |
384 KB |
Output is correct |
| 4 |
Correct |
11 ms |
896 KB |
Output is correct |
| 5 |
Correct |
9 ms |
896 KB |
Output is correct |
| 6 |
Correct |
9 ms |
896 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
180 ms |
11000 KB |
Output is correct |
| 9 |
Correct |
178 ms |
7160 KB |
Output is correct |
| 10 |
Correct |
486 ms |
13992 KB |
Output is correct |
| 11 |
Correct |
330 ms |
14456 KB |
Output is correct |
| 12 |
Correct |
307 ms |
14456 KB |
Output is correct |
| 13 |
Correct |
4 ms |
384 KB |
Output is correct |
| 14 |
Correct |
173 ms |
11256 KB |
Output is correct |
| 15 |
Correct |
39 ms |
2040 KB |
Output is correct |
| 16 |
Correct |
604 ms |
14208 KB |
Output is correct |
| 17 |
Correct |
320 ms |
14328 KB |
Output is correct |
| 18 |
Correct |
321 ms |
14200 KB |
Output is correct |
| 19 |
Correct |
741 ms |
62224 KB |
Output is correct |
| 20 |
Correct |
713 ms |
59620 KB |
Output is correct |
| 21 |
Correct |
739 ms |
61920 KB |
Output is correct |
| 22 |
Correct |
742 ms |
59472 KB |
Output is correct |
| 23 |
Correct |
721 ms |
59492 KB |
Output is correct |
| 24 |
Correct |
706 ms |
59552 KB |
Output is correct |
| 25 |
Correct |
692 ms |
59384 KB |
Output is correct |
| 26 |
Correct |
712 ms |
61944 KB |
Output is correct |
| 27 |
Correct |
723 ms |
61948 KB |
Output is correct |
| 28 |
Correct |
715 ms |
59384 KB |
Output is correct |
| 29 |
Correct |
707 ms |
59396 KB |
Output is correct |
| 30 |
Correct |
707 ms |
59340 KB |
Output is correct |
