#include <bits/stdc++.h>
using namespace std;
#include "wall.h"
struct item {
int rem , fin;
};
struct Seg {
int siz;
vector<item> sum;
item nutral = {INT_MAX , 0};
item merge(item a , item b){
item ans;
ans.fin = max(a.fin , min(b.fin , a.rem));
ans.rem = min(a.rem , b.rem);
return ans;
}
void init(int n){
siz = 1;
while(siz < n)siz *= 2;
sum.assign(siz * 2 , nutral);
}
vector<int> v;
void set(int n , int x , int lx , int rx){
if(rx - lx == 1){
if(lx < n)v.push_back(sum[x].fin);
return;
}
sum[2 * x + 1] = merge(sum[x] , sum[2 * x + 1]);
sum[2 * x + 2] = merge(sum[x] , sum[2 * x + 2]);
sum[x] = nutral;
int m = (lx + rx)/2;
set(n , 2 * x + 1 , lx , m);
set(n , 2 * x + 2 , m , rx);
}
vector<int> setall(int n){
v.clear();
set(n , 0 , 0 , siz);
return v;
}
void range_set(int l, int r , int op , int h , int x , int lx , int rx){
if(rx <= l || lx >= r){
return;
}
if(lx >= l && rx <= r){
if(op == 2){
sum[x].fin = min(sum[x].fin , h);
sum[x].rem = min(sum[x].rem , h);
}
else sum[x].fin = max(sum[x].fin , h);
return;
}
sum[2 * x + 1] = merge(sum[x] , sum[2 * x + 1]);
sum[2 * x + 2] = merge(sum[x] , sum[2 * x + 2]);
sum[x] = nutral;
int m = (lx + rx)/2;
range_set(l , r , op , h , 2 * x + 1 , lx , m);
range_set(l ,r , op , h , 2 * x + 2 , m, rx);
}
void range_set(int l , int r , int op , int h){
range_set(l , r , op , h , 0 , 0 , siz);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int hei[], int finalHeight[]){
Seg st;
st.init(n);
for(int i = 0; i < k; i++){
st.range_set(left[i] , right[i]+1 , op[i] , hei[i]);
}
vector<int> v = st.setall(n);
for(int i = 0; i < n; i++)finalHeight[i] = v[i];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
432 KB |
Output is correct |
3 |
Correct |
1 ms |
304 KB |
Output is correct |
4 |
Correct |
5 ms |
844 KB |
Output is correct |
5 |
Correct |
4 ms |
844 KB |
Output is correct |
6 |
Correct |
4 ms |
844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
150 ms |
8532 KB |
Output is correct |
3 |
Correct |
182 ms |
4592 KB |
Output is correct |
4 |
Correct |
365 ms |
11768 KB |
Output is correct |
5 |
Correct |
264 ms |
11836 KB |
Output is correct |
6 |
Correct |
280 ms |
11856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
424 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
5 ms |
816 KB |
Output is correct |
5 |
Correct |
4 ms |
748 KB |
Output is correct |
6 |
Correct |
5 ms |
844 KB |
Output is correct |
7 |
Correct |
1 ms |
284 KB |
Output is correct |
8 |
Correct |
136 ms |
8496 KB |
Output is correct |
9 |
Correct |
140 ms |
4620 KB |
Output is correct |
10 |
Correct |
361 ms |
11780 KB |
Output is correct |
11 |
Correct |
259 ms |
11836 KB |
Output is correct |
12 |
Correct |
239 ms |
11836 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
139 ms |
8480 KB |
Output is correct |
15 |
Correct |
34 ms |
1808 KB |
Output is correct |
16 |
Correct |
376 ms |
11792 KB |
Output is correct |
17 |
Correct |
247 ms |
11836 KB |
Output is correct |
18 |
Correct |
249 ms |
11772 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
3 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
5 ms |
844 KB |
Output is correct |
5 |
Correct |
7 ms |
820 KB |
Output is correct |
6 |
Correct |
5 ms |
744 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
134 ms |
8412 KB |
Output is correct |
9 |
Correct |
146 ms |
4652 KB |
Output is correct |
10 |
Correct |
384 ms |
11840 KB |
Output is correct |
11 |
Correct |
251 ms |
11800 KB |
Output is correct |
12 |
Correct |
244 ms |
11744 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
137 ms |
8388 KB |
Output is correct |
15 |
Correct |
24 ms |
1824 KB |
Output is correct |
16 |
Correct |
399 ms |
11836 KB |
Output is correct |
17 |
Correct |
245 ms |
11856 KB |
Output is correct |
18 |
Correct |
259 ms |
11892 KB |
Output is correct |
19 |
Correct |
593 ms |
64900 KB |
Output is correct |
20 |
Correct |
617 ms |
64876 KB |
Output is correct |
21 |
Correct |
608 ms |
64992 KB |
Output is correct |
22 |
Correct |
633 ms |
64972 KB |
Output is correct |
23 |
Correct |
660 ms |
64928 KB |
Output is correct |
24 |
Correct |
593 ms |
64876 KB |
Output is correct |
25 |
Correct |
601 ms |
64984 KB |
Output is correct |
26 |
Correct |
697 ms |
64868 KB |
Output is correct |
27 |
Correct |
593 ms |
64808 KB |
Output is correct |
28 |
Correct |
598 ms |
64800 KB |
Output is correct |
29 |
Correct |
625 ms |
64740 KB |
Output is correct |
30 |
Correct |
600 ms |
64740 KB |
Output is correct |