| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 18617 |
2016-02-12T14:22:13 Z |
mindol |
Wall (IOI14_wall) |
C++14 |
|
1422 ms |
49492 KB |
#include<algorithm>
using namespace std;
int lo[1<<22],hi[1<<22],base=1<<21;
void init()
{
int sz=1<<22;
for(int i=1;i<sz;i++)
lo[i]=0, hi[i]=100000;
}
void down(int now)
{
if(now>=base) return;
hi[now*2]=min(max(hi[now*2],lo[now]),hi[now]);
lo[now*2]=max(min(lo[now*2],hi[now]),lo[now]);
hi[now*2+1]=min(max(hi[now*2+1],lo[now]),hi[now]);
lo[now*2+1]=max(min(lo[now*2+1],hi[now]),lo[now]);
lo[now]=0, hi[now]=100000;
}
void update(int l,int r,int type,int value,int now,int now_l,int now_r)
{
down(now);
if(now_r<l || now_l>r) return;
else if(l<=now_l && now_r<=r)
{
if(type==0)
{
lo[now]=max(lo[now],value);
hi[now]=max(hi[now],value);
}
else
{
hi[now]=min(hi[now],value);
lo[now]=min(lo[now],value);
}
down(now);
}
else
{
int mid=(now_l+now_r)/2;
update(l,r,type,value,now*2,now_l,mid);
update(l,r,type,value,now*2+1,mid+1,now_r);
}
}
void make_res(int now,int now_l,int now_r)
{
down(now);
if(now_l==now_r) return;
int mid=(now_l+now_r)/2;
make_res(now*2,now_l,mid);
make_res(now*2+1,mid+1,now_r);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
init();
for(int i=0;i<k;i++)
update(left[i]+1,right[i]+1,op[i]-1,height[i],1,1,base);
make_res(1,1,base);
for(int i=0;i<n;i++)
finalHeight[i]=lo[i+base];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
33852 KB |
Output is correct |
| 2 |
Correct |
77 ms |
33852 KB |
Output is correct |
| 3 |
Correct |
73 ms |
33852 KB |
Output is correct |
| 4 |
Correct |
77 ms |
33852 KB |
Output is correct |
| 5 |
Correct |
80 ms |
33852 KB |
Output is correct |
| 6 |
Correct |
76 ms |
33852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
33852 KB |
Output is correct |
| 2 |
Correct |
727 ms |
41676 KB |
Output is correct |
| 3 |
Correct |
453 ms |
37100 KB |
Output is correct |
| 4 |
Correct |
1091 ms |
42068 KB |
Output is correct |
| 5 |
Correct |
702 ms |
42068 KB |
Output is correct |
| 6 |
Correct |
727 ms |
42068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
33852 KB |
Output is correct |
| 2 |
Correct |
78 ms |
33852 KB |
Output is correct |
| 3 |
Correct |
74 ms |
33852 KB |
Output is correct |
| 4 |
Correct |
76 ms |
33852 KB |
Output is correct |
| 5 |
Correct |
76 ms |
33852 KB |
Output is correct |
| 6 |
Correct |
80 ms |
33852 KB |
Output is correct |
| 7 |
Correct |
67 ms |
33852 KB |
Output is correct |
| 8 |
Correct |
764 ms |
41676 KB |
Output is correct |
| 9 |
Correct |
457 ms |
37100 KB |
Output is correct |
| 10 |
Correct |
1087 ms |
42068 KB |
Output is correct |
| 11 |
Correct |
720 ms |
42068 KB |
Output is correct |
| 12 |
Correct |
690 ms |
42068 KB |
Output is correct |
| 13 |
Correct |
70 ms |
33852 KB |
Output is correct |
| 14 |
Correct |
761 ms |
41676 KB |
Output is correct |
| 15 |
Correct |
134 ms |
34336 KB |
Output is correct |
| 16 |
Correct |
1134 ms |
42068 KB |
Output is correct |
| 17 |
Correct |
722 ms |
42068 KB |
Output is correct |
| 18 |
Correct |
732 ms |
42068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
33852 KB |
Output is correct |
| 2 |
Correct |
72 ms |
33852 KB |
Output is correct |
| 3 |
Correct |
69 ms |
33852 KB |
Output is correct |
| 4 |
Correct |
81 ms |
33852 KB |
Output is correct |
| 5 |
Correct |
80 ms |
33852 KB |
Output is correct |
| 6 |
Correct |
83 ms |
33852 KB |
Output is correct |
| 7 |
Correct |
70 ms |
33852 KB |
Output is correct |
| 8 |
Correct |
774 ms |
41676 KB |
Output is correct |
| 9 |
Correct |
468 ms |
37100 KB |
Output is correct |
| 10 |
Correct |
1084 ms |
42068 KB |
Output is correct |
| 11 |
Correct |
722 ms |
42068 KB |
Output is correct |
| 12 |
Correct |
732 ms |
42068 KB |
Output is correct |
| 13 |
Correct |
70 ms |
33852 KB |
Output is correct |
| 14 |
Correct |
759 ms |
41676 KB |
Output is correct |
| 15 |
Correct |
124 ms |
34336 KB |
Output is correct |
| 16 |
Correct |
1115 ms |
42068 KB |
Output is correct |
| 17 |
Correct |
709 ms |
42068 KB |
Output is correct |
| 18 |
Correct |
747 ms |
42068 KB |
Output is correct |
| 19 |
Correct |
1369 ms |
49492 KB |
Output is correct |
| 20 |
Correct |
1384 ms |
49492 KB |
Output is correct |
| 21 |
Correct |
1369 ms |
49492 KB |
Output is correct |
| 22 |
Correct |
1390 ms |
49492 KB |
Output is correct |
| 23 |
Correct |
1344 ms |
49492 KB |
Output is correct |
| 24 |
Correct |
1373 ms |
49492 KB |
Output is correct |
| 25 |
Correct |
1317 ms |
49492 KB |
Output is correct |
| 26 |
Correct |
1353 ms |
49492 KB |
Output is correct |
| 27 |
Correct |
1381 ms |
49492 KB |
Output is correct |
| 28 |
Correct |
1422 ms |
49492 KB |
Output is correct |
| 29 |
Correct |
1398 ms |
49492 KB |
Output is correct |
| 30 |
Correct |
1364 ms |
49492 KB |
Output is correct |
