| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 12192 |
2014-12-22T14:25:59 Z |
ho94949 |
Wall (IOI14_wall) |
C++ |
|
1148 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){
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
25664 KB |
Output is correct |
| 2 |
Correct |
12 ms |
25664 KB |
Output is correct |
| 3 |
Correct |
16 ms |
25664 KB |
Output is correct |
| 4 |
Correct |
8 ms |
25664 KB |
Output is correct |
| 5 |
Correct |
12 ms |
25664 KB |
Output is correct |
| 6 |
Correct |
8 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 |
348 ms |
28912 KB |
Output is correct |
| 4 |
Correct |
972 ms |
33880 KB |
Output is correct |
| 5 |
Correct |
428 ms |
33880 KB |
Output is correct |
| 6 |
Correct |
400 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 |
12 ms |
25664 KB |
Output is correct |
| 4 |
Correct |
24 ms |
25664 KB |
Output is correct |
| 5 |
Correct |
16 ms |
25664 KB |
Output is correct |
| 6 |
Correct |
8 ms |
25664 KB |
Output is correct |
| 7 |
Correct |
4 ms |
25664 KB |
Output is correct |
| 8 |
Correct |
360 ms |
33488 KB |
Output is correct |
| 9 |
Correct |
352 ms |
28912 KB |
Output is correct |
| 10 |
Correct |
972 ms |
33880 KB |
Output is correct |
| 11 |
Correct |
432 ms |
33880 KB |
Output is correct |
| 12 |
Correct |
404 ms |
33880 KB |
Output is correct |
| 13 |
Correct |
4 ms |
25664 KB |
Output is correct |
| 14 |
Correct |
372 ms |
33488 KB |
Output is correct |
| 15 |
Correct |
64 ms |
26148 KB |
Output is correct |
| 16 |
Correct |
1148 ms |
33880 KB |
Output is correct |
| 17 |
Correct |
428 ms |
33880 KB |
Output is correct |
| 18 |
Correct |
424 ms |
33880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
25664 KB |
Output is correct |
| 2 |
Correct |
8 ms |
25664 KB |
Output is correct |
| 3 |
Correct |
16 ms |
25664 KB |
Output is correct |
| 4 |
Correct |
20 ms |
25664 KB |
Output is correct |
| 5 |
Correct |
8 ms |
25664 KB |
Output is correct |
| 6 |
Correct |
16 ms |
25664 KB |
Output is correct |
| 7 |
Correct |
8 ms |
25664 KB |
Output is correct |
| 8 |
Correct |
384 ms |
33488 KB |
Output is correct |
| 9 |
Correct |
356 ms |
28912 KB |
Output is correct |
| 10 |
Correct |
972 ms |
33880 KB |
Output is correct |
| 11 |
Correct |
412 ms |
33880 KB |
Output is correct |
| 12 |
Correct |
416 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 |
1124 ms |
33880 KB |
Output is correct |
| 17 |
Correct |
416 ms |
33880 KB |
Output is correct |
| 18 |
Correct |
400 ms |
33880 KB |
Output is correct |
| 19 |
Runtime error |
468 ms |
41300 KB |
Program hung waiting for input |
| 20 |
Halted |
0 ms |
0 KB |
- |
