| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 18408 |
2016-01-31T12:31:11 Z |
chan492811 |
Wall (IOI14_wall) |
C++ |
|
1069 ms |
141724 KB |
#include <algorithm>
#define INF 2100000000
using namespace std;
int n,m,tn=1;
struct data{
int maxh,minh,l,r;
};
data tree[8000010];
void make_tree(int a){
if(a>=tn) return;
make_tree(a*2); make_tree(a*2+1);
if(tree[a*2].l==0) return;
if(tree[a*2+1].l==0){ tree[a]=tree[a*2]; return; }
tree[a].l=tree[a*2].l; tree[a].r=tree[a*2+1].r;
}
void update_node(int flag,int a,int h){
if(flag==1){
tree[a].maxh=max(tree[a].maxh,h);
tree[a].minh=max(tree[a].minh,h);
}else{
tree[a].maxh=min(tree[a].maxh,h);
tree[a].minh=min(tree[a].minh,h);
}
}
void update(int flag,int a,int l,int r,int h){
if(tree[a].l==0 || tree[a].r<l || tree[a].l>r) return;
if(tree[a].l>=l && tree[a].r<=r){
update_node(flag,a,h);
}else{
update_node(1,a*2,tree[a].minh);
update_node(2,a*2,tree[a].maxh);
update_node(1,a*2+1,tree[a].minh);
update_node(2,a*2+1,tree[a].maxh);
tree[a].maxh=INF; tree[a].minh=0;
update(flag,a*2,l,r,h); update(flag,a*2+1,l,r,h);
}
}
void finalupdate(int a){
if(tree[a].l==0 || a>=tn) return;
update_node(1,a*2,tree[a].minh);
update_node(2,a*2,tree[a].maxh);
update_node(1,a*2+1,tree[a].minh);
update_node(2,a*2+1,tree[a].maxh);
tree[a].maxh=INF; tree[a].minh=0;
finalupdate(a*2); finalupdate(a*2+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
int i;
while(tn<n)tn*=2;
for(i=tn;i<tn+n;i++) tree[i].l=i-tn+1,tree[i].r=i-tn+1;
make_tree(1);
for(i=0;i<k;i++){
update(op[i],1,left[i]+1,right[i]+1,height[i]);
}
finalupdate(1);
for(i=tn;i<tn+n;i++) finalHeight[i-tn]=tree[i].maxh;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
126084 KB |
Output is correct |
| 2 |
Correct |
0 ms |
126084 KB |
Output is correct |
| 3 |
Correct |
0 ms |
126084 KB |
Output is correct |
| 4 |
Correct |
7 ms |
126084 KB |
Output is correct |
| 5 |
Correct |
8 ms |
126084 KB |
Output is correct |
| 6 |
Correct |
6 ms |
126084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
126084 KB |
Output is correct |
| 2 |
Correct |
170 ms |
133908 KB |
Output is correct |
| 3 |
Correct |
240 ms |
129332 KB |
Output is correct |
| 4 |
Correct |
617 ms |
134300 KB |
Output is correct |
| 5 |
Correct |
457 ms |
134300 KB |
Output is correct |
| 6 |
Correct |
442 ms |
134300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
126084 KB |
Output is correct |
| 2 |
Correct |
0 ms |
126084 KB |
Output is correct |
| 3 |
Correct |
0 ms |
126084 KB |
Output is correct |
| 4 |
Correct |
7 ms |
126084 KB |
Output is correct |
| 5 |
Correct |
7 ms |
126084 KB |
Output is correct |
| 6 |
Correct |
6 ms |
126084 KB |
Output is correct |
| 7 |
Correct |
0 ms |
126084 KB |
Output is correct |
| 8 |
Correct |
169 ms |
133908 KB |
Output is correct |
| 9 |
Correct |
248 ms |
129332 KB |
Output is correct |
| 10 |
Correct |
785 ms |
134300 KB |
Output is correct |
| 11 |
Correct |
451 ms |
134300 KB |
Output is correct |
| 12 |
Correct |
478 ms |
134300 KB |
Output is correct |
| 13 |
Correct |
0 ms |
126084 KB |
Output is correct |
| 14 |
Correct |
126 ms |
133908 KB |
Output is correct |
| 15 |
Correct |
43 ms |
126568 KB |
Output is correct |
| 16 |
Correct |
737 ms |
134300 KB |
Output is correct |
| 17 |
Correct |
444 ms |
134300 KB |
Output is correct |
| 18 |
Correct |
479 ms |
134300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
126084 KB |
Output is correct |
| 2 |
Correct |
0 ms |
126084 KB |
Output is correct |
| 3 |
Correct |
0 ms |
126084 KB |
Output is correct |
| 4 |
Correct |
4 ms |
126084 KB |
Output is correct |
| 5 |
Correct |
6 ms |
126084 KB |
Output is correct |
| 6 |
Correct |
3 ms |
126084 KB |
Output is correct |
| 7 |
Correct |
0 ms |
126084 KB |
Output is correct |
| 8 |
Correct |
175 ms |
133908 KB |
Output is correct |
| 9 |
Correct |
255 ms |
129332 KB |
Output is correct |
| 10 |
Correct |
732 ms |
134300 KB |
Output is correct |
| 11 |
Correct |
508 ms |
134300 KB |
Output is correct |
| 12 |
Correct |
466 ms |
134300 KB |
Output is correct |
| 13 |
Correct |
0 ms |
126084 KB |
Output is correct |
| 14 |
Correct |
169 ms |
133908 KB |
Output is correct |
| 15 |
Correct |
43 ms |
126568 KB |
Output is correct |
| 16 |
Correct |
745 ms |
134300 KB |
Output is correct |
| 17 |
Correct |
413 ms |
134300 KB |
Output is correct |
| 18 |
Correct |
485 ms |
134300 KB |
Output is correct |
| 19 |
Correct |
1047 ms |
141724 KB |
Output is correct |
| 20 |
Correct |
992 ms |
141724 KB |
Output is correct |
| 21 |
Correct |
1000 ms |
141724 KB |
Output is correct |
| 22 |
Correct |
1011 ms |
141724 KB |
Output is correct |
| 23 |
Correct |
1007 ms |
141724 KB |
Output is correct |
| 24 |
Correct |
964 ms |
141724 KB |
Output is correct |
| 25 |
Correct |
854 ms |
141724 KB |
Output is correct |
| 26 |
Correct |
981 ms |
141724 KB |
Output is correct |
| 27 |
Correct |
1005 ms |
141724 KB |
Output is correct |
| 28 |
Correct |
1017 ms |
141724 KB |
Output is correct |
| 29 |
Correct |
1069 ms |
141724 KB |
Output is correct |
| 30 |
Correct |
851 ms |
141724 KB |
Output is correct |
