| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 12191 |
2014-12-22T14:24:25 Z |
ho94949 |
Wall (IOI14_wall) |
C++ |
|
1128 ms |
41300 KB |
#include "wall.h"
#include <algorithm>
#define N 1048576
#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){
// [minh[2*ind],maxh[2*ind]]
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){
//fprintf(stderr,"%d %d %d %d %d %d %d\n",ind,indleft,indright,minv,maxv,left,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 j=1;j<2*N;j++) printf("%d: %d %d %d\n",j, seg[j],minh[j],maxh[j]);
//puts("=====");
}
for(int i=1;i<N+n;i++) updatelazy(i);
for(int i=0;i<n;i++) finalHeight[i]=seg[N+i];
return;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
25664 KB |
Output is correct |
| 2 |
Correct |
4 ms |
25664 KB |
Output is correct |
| 3 |
Correct |
12 ms |
25664 KB |
Output is correct |
| 4 |
Correct |
16 ms |
25664 KB |
Output is correct |
| 5 |
Correct |
16 ms |
25664 KB |
Output is correct |
| 6 |
Correct |
12 ms |
25664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
25664 KB |
Output is correct |
| 2 |
Correct |
368 ms |
33488 KB |
Output is correct |
| 3 |
Correct |
352 ms |
28912 KB |
Output is correct |
| 4 |
Correct |
980 ms |
33880 KB |
Output is correct |
| 5 |
Correct |
420 ms |
33880 KB |
Output is correct |
| 6 |
Correct |
408 ms |
33880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
25664 KB |
Output is correct |
| 2 |
Correct |
12 ms |
25664 KB |
Output is correct |
| 3 |
Correct |
12 ms |
25664 KB |
Output is correct |
| 4 |
Correct |
12 ms |
25664 KB |
Output is correct |
| 5 |
Correct |
12 ms |
25664 KB |
Output is correct |
| 6 |
Correct |
16 ms |
25664 KB |
Output is correct |
| 7 |
Correct |
4 ms |
25664 KB |
Output is correct |
| 8 |
Correct |
364 ms |
33488 KB |
Output is correct |
| 9 |
Correct |
352 ms |
28912 KB |
Output is correct |
| 10 |
Correct |
988 ms |
33880 KB |
Output is correct |
| 11 |
Correct |
408 ms |
33880 KB |
Output is correct |
| 12 |
Correct |
412 ms |
33880 KB |
Output is correct |
| 13 |
Correct |
12 ms |
25664 KB |
Output is correct |
| 14 |
Correct |
376 ms |
33488 KB |
Output is correct |
| 15 |
Correct |
68 ms |
26148 KB |
Output is correct |
| 16 |
Correct |
1124 ms |
33880 KB |
Output is correct |
| 17 |
Correct |
424 ms |
33880 KB |
Output is correct |
| 18 |
Correct |
420 ms |
33880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
25664 KB |
Output is correct |
| 2 |
Correct |
8 ms |
25664 KB |
Output is correct |
| 3 |
Correct |
4 ms |
25664 KB |
Output is correct |
| 4 |
Correct |
16 ms |
25664 KB |
Output is correct |
| 5 |
Correct |
12 ms |
25664 KB |
Output is correct |
| 6 |
Correct |
12 ms |
25664 KB |
Output is correct |
| 7 |
Correct |
4 ms |
25664 KB |
Output is correct |
| 8 |
Correct |
364 ms |
33488 KB |
Output is correct |
| 9 |
Correct |
348 ms |
28912 KB |
Output is correct |
| 10 |
Correct |
968 ms |
33880 KB |
Output is correct |
| 11 |
Correct |
420 ms |
33880 KB |
Output is correct |
| 12 |
Correct |
400 ms |
33880 KB |
Output is correct |
| 13 |
Correct |
12 ms |
25664 KB |
Output is correct |
| 14 |
Correct |
364 ms |
33488 KB |
Output is correct |
| 15 |
Correct |
64 ms |
26148 KB |
Output is correct |
| 16 |
Correct |
1128 ms |
33880 KB |
Output is correct |
| 17 |
Correct |
412 ms |
33880 KB |
Output is correct |
| 18 |
Correct |
408 ms |
33880 KB |
Output is correct |
| 19 |
Runtime error |
460 ms |
41300 KB |
Program hung waiting for input |
| 20 |
Halted |
0 ms |
0 KB |
- |
