# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
43765 |
2018-03-23T03:40:15 Z |
faustaadp |
Wall (IOI14_wall) |
C++14 |
|
886 ms |
262144 KB |
#include "wall.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll i,mi[8080808],ma[8080808],h[2020202];
bool lz[8080808];
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(lz[ee])
{
lz[ee]=0;
lz[ee*2]=1;
lz[ee*2+1]=1;
tum(ee*2,mi[ee],ma[ee]);
tum(ee*2+1,mi[ee],ma[ee]);
mi[ee]=1e17;
ma[ee]=0;
}
if(bb<cc||dd<aa)
return ;
else
if(cc<=aa&&bb<=dd)
{
lz[ee]=1;
tum(ee,ff,gg);
}
else
{
ll ce=(aa+bb)/2;
upd(aa,ce,cc,dd,ee*2,ff,gg);
upd(ce+1,bb,cc,dd,ee*2+1,ff,gg);
}
}
void final(ll aa,ll bb,ll ee)
{
if(aa==bb)
{
h[aa]=ma[ee];
return ;
}
else
if(lz[ee])
{
lz[ee]=0;
lz[ee*2]=1;
lz[ee*2+1]=1;
tum(ee*2,mi[ee],ma[ee]);
tum(ee*2+1,mi[ee],ma[ee]);
mi[ee]=1e17;
ma[ee]=0;
}
ll ce=(aa+bb)/2;
final(aa,ce,ee*2);
final(ce+1,bb,ee*2+1);
}
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);
}
final(0,n-1,1);
for(i=0;i<n;i++)
finalHeight[i]=h[i];
return ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
4 ms |
620 KB |
Output is correct |
3 |
Correct |
3 ms |
620 KB |
Output is correct |
4 |
Correct |
8 ms |
1636 KB |
Output is correct |
5 |
Correct |
7 ms |
1844 KB |
Output is correct |
6 |
Correct |
6 ms |
2000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2000 KB |
Output is correct |
2 |
Correct |
168 ms |
14652 KB |
Output is correct |
3 |
Correct |
241 ms |
15480 KB |
Output is correct |
4 |
Correct |
816 ms |
35180 KB |
Output is correct |
5 |
Correct |
383 ms |
45696 KB |
Output is correct |
6 |
Correct |
299 ms |
54380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
54380 KB |
Output is correct |
2 |
Correct |
4 ms |
54380 KB |
Output is correct |
3 |
Correct |
3 ms |
54380 KB |
Output is correct |
4 |
Correct |
8 ms |
54380 KB |
Output is correct |
5 |
Correct |
7 ms |
54380 KB |
Output is correct |
6 |
Correct |
6 ms |
54380 KB |
Output is correct |
7 |
Correct |
2 ms |
54380 KB |
Output is correct |
8 |
Correct |
181 ms |
54380 KB |
Output is correct |
9 |
Correct |
228 ms |
54380 KB |
Output is correct |
10 |
Correct |
826 ms |
73340 KB |
Output is correct |
11 |
Correct |
338 ms |
84076 KB |
Output is correct |
12 |
Correct |
302 ms |
92640 KB |
Output is correct |
13 |
Correct |
2 ms |
92640 KB |
Output is correct |
14 |
Correct |
193 ms |
92640 KB |
Output is correct |
15 |
Correct |
37 ms |
92640 KB |
Output is correct |
16 |
Correct |
786 ms |
108372 KB |
Output is correct |
17 |
Correct |
315 ms |
117548 KB |
Output is correct |
18 |
Correct |
319 ms |
126440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
126440 KB |
Output is correct |
2 |
Correct |
5 ms |
126440 KB |
Output is correct |
3 |
Correct |
3 ms |
126440 KB |
Output is correct |
4 |
Correct |
13 ms |
126440 KB |
Output is correct |
5 |
Correct |
7 ms |
126440 KB |
Output is correct |
6 |
Correct |
7 ms |
126440 KB |
Output is correct |
7 |
Correct |
2 ms |
126440 KB |
Output is correct |
8 |
Correct |
218 ms |
126440 KB |
Output is correct |
9 |
Correct |
229 ms |
126440 KB |
Output is correct |
10 |
Correct |
754 ms |
145940 KB |
Output is correct |
11 |
Correct |
327 ms |
156604 KB |
Output is correct |
12 |
Correct |
316 ms |
165232 KB |
Output is correct |
13 |
Correct |
2 ms |
165232 KB |
Output is correct |
14 |
Correct |
171 ms |
165232 KB |
Output is correct |
15 |
Correct |
36 ms |
165232 KB |
Output is correct |
16 |
Correct |
783 ms |
180980 KB |
Output is correct |
17 |
Correct |
324 ms |
190008 KB |
Output is correct |
18 |
Correct |
322 ms |
199164 KB |
Output is correct |
19 |
Correct |
886 ms |
262144 KB |
Output is correct |
20 |
Correct |
806 ms |
262144 KB |
Output is correct |
21 |
Correct |
874 ms |
262144 KB |
Output is correct |
22 |
Correct |
855 ms |
262144 KB |
Output is correct |
23 |
Correct |
820 ms |
262144 KB |
Output is correct |
24 |
Correct |
833 ms |
262144 KB |
Output is correct |
25 |
Correct |
855 ms |
262144 KB |
Output is correct |
26 |
Correct |
827 ms |
262144 KB |
Output is correct |
27 |
Correct |
823 ms |
262144 KB |
Output is correct |
28 |
Correct |
829 ms |
262144 KB |
Output is correct |
29 |
Correct |
796 ms |
262144 KB |
Output is correct |
30 |
Correct |
821 ms |
262144 KB |
Output is correct |