#include "wall.h"
#include <algorithm>
#define N 2097152
#define INF 987654321
int seg[2*N];
int minh[2*N];
int maxh[2*N];
void updatelazy(int ind){
if(minh[ind]==-INF) return;
seg[ind]=std::max(seg[ind],minh[ind]);
seg[ind]=std::min(seg[ind],maxh[ind]);
if(ind<N){
if(maxh[2*ind]<minh[ind]) minh[2*ind]=maxh[2*ind]=minh[ind];
if(maxh[ind]<minh[2*ind]) minh[2*ind]=maxh[2*ind]=maxh[ind];
maxh[2*ind]=std::min(maxh[ind],maxh[2*ind]);
minh[2*ind]=std::max(minh[ind],minh[2*ind]);
if(maxh[2*ind+1]<minh[ind]) minh[2*ind+1]=maxh[2*ind+1]=minh[ind];
if(maxh[ind]<minh[2*ind+1]) minh[2*ind+1]=maxh[2*ind+1]=maxh[ind];
maxh[2*ind+1]=std::min(maxh[ind],maxh[2*ind+1]);
minh[2*ind+1]=std::max(minh[ind],minh[2*ind+1]);
}
minh[ind]=-INF;
maxh[ind]=INF;
return;
}
void set(int ind,int indleft,int indright,int minv,int maxv,int left,int right){
if(left<=indleft && indright <=right){
if(maxh[ind]<minv) maxh[ind]=minh[ind]=minv;
if(maxv<minh[ind]) minh[ind]=maxh[ind]=maxv;
maxh[ind]=std::min(maxh[ind],maxv);
minh[ind]=std::max(minh[ind],minv);
updatelazy(ind);
return;
}
updatelazy(ind);
if(indright<left || right < indleft) return;
if(ind<N){
set(2*ind,indleft,(indleft+indright)/2,minv,maxv,left,right);
set(2*ind+1,(indleft+indright)/2+1,indright,minv,maxv,left,right);
}
return;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=1;i<2*N;i++) minh[i]=-INF,maxh[i]=INF;
for(int i=0;i<k;i++){
if(op[i]==2) set(1,0,N-1,0,height[i],left[i],right[i]);
else set(1,0,N-1,height[i],INF,left[i],right[i]);
}
for(int i=1;i<N+n;i++) updatelazy(i);
for(int i=0;i<n;i++) finalHeight[i]=seg[N+i];
return;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
50240 KB |
Output is correct |
| 2 |
Correct |
20 ms |
50240 KB |
Output is correct |
| 3 |
Correct |
16 ms |
50240 KB |
Output is correct |
| 4 |
Correct |
24 ms |
50240 KB |
Output is correct |
| 5 |
Correct |
16 ms |
50240 KB |
Output is correct |
| 6 |
Correct |
20 ms |
50240 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
50240 KB |
Output is correct |
| 2 |
Correct |
392 ms |
58064 KB |
Output is correct |
| 3 |
Correct |
388 ms |
53488 KB |
Output is correct |
| 4 |
Correct |
1016 ms |
58456 KB |
Output is correct |
| 5 |
Correct |
424 ms |
58456 KB |
Output is correct |
| 6 |
Correct |
428 ms |
58456 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
50240 KB |
Output is correct |
| 2 |
Correct |
16 ms |
50240 KB |
Output is correct |
| 3 |
Correct |
16 ms |
50240 KB |
Output is correct |
| 4 |
Correct |
28 ms |
50240 KB |
Output is correct |
| 5 |
Correct |
16 ms |
50240 KB |
Output is correct |
| 6 |
Correct |
16 ms |
50240 KB |
Output is correct |
| 7 |
Correct |
12 ms |
50240 KB |
Output is correct |
| 8 |
Correct |
376 ms |
58064 KB |
Output is correct |
| 9 |
Correct |
388 ms |
53488 KB |
Output is correct |
| 10 |
Correct |
1020 ms |
58456 KB |
Output is correct |
| 11 |
Correct |
432 ms |
58456 KB |
Output is correct |
| 12 |
Correct |
432 ms |
58456 KB |
Output is correct |
| 13 |
Correct |
16 ms |
50240 KB |
Output is correct |
| 14 |
Correct |
392 ms |
58064 KB |
Output is correct |
| 15 |
Correct |
80 ms |
50724 KB |
Output is correct |
| 16 |
Correct |
1164 ms |
58456 KB |
Output is correct |
| 17 |
Correct |
432 ms |
58456 KB |
Output is correct |
| 18 |
Correct |
428 ms |
58456 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
50240 KB |
Output is correct |
| 2 |
Correct |
16 ms |
50240 KB |
Output is correct |
| 3 |
Correct |
12 ms |
50240 KB |
Output is correct |
| 4 |
Correct |
20 ms |
50240 KB |
Output is correct |
| 5 |
Correct |
16 ms |
50240 KB |
Output is correct |
| 6 |
Correct |
20 ms |
50240 KB |
Output is correct |
| 7 |
Correct |
12 ms |
50240 KB |
Output is correct |
| 8 |
Correct |
392 ms |
58064 KB |
Output is correct |
| 9 |
Correct |
372 ms |
53488 KB |
Output is correct |
| 10 |
Correct |
1020 ms |
58456 KB |
Output is correct |
| 11 |
Correct |
440 ms |
58456 KB |
Output is correct |
| 12 |
Correct |
424 ms |
58456 KB |
Output is correct |
| 13 |
Correct |
20 ms |
50240 KB |
Output is correct |
| 14 |
Correct |
392 ms |
58064 KB |
Output is correct |
| 15 |
Correct |
80 ms |
50724 KB |
Output is correct |
| 16 |
Correct |
1180 ms |
58456 KB |
Output is correct |
| 17 |
Correct |
420 ms |
58456 KB |
Output is correct |
| 18 |
Correct |
432 ms |
58456 KB |
Output is correct |
| 19 |
Correct |
972 ms |
65880 KB |
Output is correct |
| 20 |
Correct |
976 ms |
65880 KB |
Output is correct |
| 21 |
Correct |
976 ms |
65880 KB |
Output is correct |
| 22 |
Correct |
988 ms |
65880 KB |
Output is correct |
| 23 |
Correct |
992 ms |
65880 KB |
Output is correct |
| 24 |
Correct |
1004 ms |
65880 KB |
Output is correct |
| 25 |
Correct |
972 ms |
65880 KB |
Output is correct |
| 26 |
Correct |
976 ms |
65880 KB |
Output is correct |
| 27 |
Correct |
1012 ms |
65880 KB |
Output is correct |
| 28 |
Correct |
988 ms |
65880 KB |
Output is correct |
| 29 |
Correct |
1008 ms |
65880 KB |
Output is correct |
| 30 |
Correct |
972 ms |
65880 KB |
Output is correct |
