| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 43767 |
2018-03-23T04:13:49 Z |
faustaadp |
Wall (IOI14_wall) |
C++14 |
|
927 ms |
199448 KB |
#include "wall.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll i,mi[8080808],ma[8080808],h[2020202];
void tum(ll aa,ll bb,ll cc)
{
mi[aa]=min(mi[aa],bb);
ma[aa]=min(ma[aa],bb);
ma[aa]=max(ma[aa],cc);
}
void upd(ll aa,ll bb,ll cc,ll dd,ll ee,ll ff,ll gg)
{
if(aa==bb)
h[aa]=ma[ee];
else
if(mi[ee]!=1e17||ma[ee]!=0)
{
tum(ee*2,mi[ee],ma[ee]);
tum(ee*2+1,mi[ee],ma[ee]);
mi[ee]=1e17;
ma[ee]=0;
}
if(cc!=-1&&(bb<cc||dd<aa))
return ;
else
if(cc!=-1&&cc<=aa&&bb<=dd)
tum(ee,ff,gg);
else
{
if(aa==bb) return ;
upd(aa,(aa+bb)/2,cc,dd,ee*2,ff,gg);
upd((aa+bb)/2+1,bb,cc,dd,ee*2+1,ff,gg);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(i=1;i<=4*n;i++)
mi[i]=1e17;
for(i=0;i<k;i++)
if(op[i]==1)
upd(0,n-1,left[i],right[i],1,1e17,height[i]);
else
upd(0,n-1,left[i],right[i],1,height[i],0);
upd(0,n-1,-1,-1,1,1e17,0);
for(i=0;i<n;i++)
finalHeight[i]=h[i];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
484 KB |
Output is correct |
| 3 |
Correct |
3 ms |
648 KB |
Output is correct |
| 4 |
Correct |
9 ms |
1520 KB |
Output is correct |
| 5 |
Correct |
8 ms |
1556 KB |
Output is correct |
| 6 |
Correct |
11 ms |
1716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1716 KB |
Output is correct |
| 2 |
Correct |
173 ms |
14688 KB |
Output is correct |
| 3 |
Correct |
222 ms |
15156 KB |
Output is correct |
| 4 |
Correct |
742 ms |
34660 KB |
Output is correct |
| 5 |
Correct |
321 ms |
45188 KB |
Output is correct |
| 6 |
Correct |
345 ms |
53828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
53828 KB |
Output is correct |
| 2 |
Correct |
4 ms |
53828 KB |
Output is correct |
| 3 |
Correct |
3 ms |
53828 KB |
Output is correct |
| 4 |
Correct |
12 ms |
53828 KB |
Output is correct |
| 5 |
Correct |
9 ms |
53828 KB |
Output is correct |
| 6 |
Correct |
8 ms |
53828 KB |
Output is correct |
| 7 |
Correct |
2 ms |
53828 KB |
Output is correct |
| 8 |
Correct |
172 ms |
53828 KB |
Output is correct |
| 9 |
Correct |
217 ms |
53828 KB |
Output is correct |
| 10 |
Correct |
753 ms |
72928 KB |
Output is correct |
| 11 |
Correct |
378 ms |
77312 KB |
Output is correct |
| 12 |
Correct |
323 ms |
77452 KB |
Output is correct |
| 13 |
Correct |
2 ms |
77452 KB |
Output is correct |
| 14 |
Correct |
182 ms |
77452 KB |
Output is correct |
| 15 |
Correct |
43 ms |
77452 KB |
Output is correct |
| 16 |
Correct |
768 ms |
77452 KB |
Output is correct |
| 17 |
Correct |
352 ms |
77452 KB |
Output is correct |
| 18 |
Correct |
336 ms |
77452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
77452 KB |
Output is correct |
| 2 |
Correct |
3 ms |
77452 KB |
Output is correct |
| 3 |
Correct |
3 ms |
77452 KB |
Output is correct |
| 4 |
Correct |
13 ms |
77452 KB |
Output is correct |
| 5 |
Correct |
7 ms |
77452 KB |
Output is correct |
| 6 |
Correct |
8 ms |
77452 KB |
Output is correct |
| 7 |
Correct |
2 ms |
77452 KB |
Output is correct |
| 8 |
Correct |
181 ms |
77452 KB |
Output is correct |
| 9 |
Correct |
241 ms |
77452 KB |
Output is correct |
| 10 |
Correct |
767 ms |
77452 KB |
Output is correct |
| 11 |
Correct |
339 ms |
77452 KB |
Output is correct |
| 12 |
Correct |
349 ms |
77452 KB |
Output is correct |
| 13 |
Correct |
2 ms |
77452 KB |
Output is correct |
| 14 |
Correct |
176 ms |
77452 KB |
Output is correct |
| 15 |
Correct |
48 ms |
77452 KB |
Output is correct |
| 16 |
Correct |
750 ms |
77452 KB |
Output is correct |
| 17 |
Correct |
323 ms |
77452 KB |
Output is correct |
| 18 |
Correct |
336 ms |
77452 KB |
Output is correct |
| 19 |
Correct |
927 ms |
199144 KB |
Output is correct |
| 20 |
Correct |
849 ms |
199144 KB |
Output is correct |
| 21 |
Correct |
909 ms |
199348 KB |
Output is correct |
| 22 |
Correct |
830 ms |
199348 KB |
Output is correct |
| 23 |
Correct |
841 ms |
199348 KB |
Output is correct |
| 24 |
Correct |
912 ms |
199348 KB |
Output is correct |
| 25 |
Correct |
837 ms |
199348 KB |
Output is correct |
| 26 |
Correct |
874 ms |
199448 KB |
Output is correct |
| 27 |
Correct |
869 ms |
199448 KB |
Output is correct |
| 28 |
Correct |
884 ms |
199448 KB |
Output is correct |
| 29 |
Correct |
852 ms |
199448 KB |
Output is correct |
| 30 |
Correct |
891 ms |
199448 KB |
Output is correct |
