| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 291933 |
2020-09-06T03:44:00 Z |
TMJN |
Wall (IOI14_wall) |
C++17 |
|
816 ms |
69628 KB |
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
pair<int,int>tree[1<<22];
pair<int,int>merge(pair<int,int>x,pair<int,int>y){
pair<int,int>p={min(x.first,y.first),max(x.second,y.second)};
if(p.first<p.second){
if(x.second>y.first){
p.second=p.first;
}
else{
p.first=p.second;
}
}
return p;
}
void update(int k,int l,int r,int p,int q,pair<int,int>val){
if(q<l||r<p)return;
else if(p<=l&&r<=q){
tree[k]=merge(tree[k],val);
}
else{
tree[k+k]=merge(tree[k+k],tree[k]);
tree[k+k+1]=merge(tree[k+k+1],tree[k]);
tree[k]={0xE869120,0};
update(k+k,l,(l+r)/2,p,q,val);
update(k+k+1,(l+r)/2+1,r,p,q,val);
}
}
int calc(int x){
pair<int,int>a={0,0};
x+=(1<<21);
while(x){
a=merge(a,tree[x]);
x/=2;
}
return a.first;
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0;i<(1<<22);i++){
tree[i]={0,0};
}
for(int i=0;i<K;i++){
if(op[i]==1){
update(1,0,(1<<21)-1,left[i],right[i],pair<int,int>{0xE869120,height[i]});
}
else{
update(1,0,(1<<21)-1,left[i],right[i],pair<int,int>{height[i],0});
}
}
for(int i=0;i<N;i++){
finalHeight[i]=calc(i);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
33152 KB |
Output is correct |
| 2 |
Correct |
23 ms |
33272 KB |
Output is correct |
| 3 |
Correct |
21 ms |
33152 KB |
Output is correct |
| 4 |
Correct |
27 ms |
33408 KB |
Output is correct |
| 5 |
Correct |
25 ms |
33408 KB |
Output is correct |
| 6 |
Correct |
25 ms |
33400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
33152 KB |
Output is correct |
| 2 |
Correct |
336 ms |
46840 KB |
Output is correct |
| 3 |
Correct |
214 ms |
40312 KB |
Output is correct |
| 4 |
Correct |
559 ms |
51192 KB |
Output is correct |
| 5 |
Correct |
377 ms |
52216 KB |
Output is correct |
| 6 |
Correct |
357 ms |
50680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
33280 KB |
Output is correct |
| 2 |
Correct |
22 ms |
33280 KB |
Output is correct |
| 3 |
Correct |
21 ms |
33152 KB |
Output is correct |
| 4 |
Correct |
26 ms |
33408 KB |
Output is correct |
| 5 |
Correct |
25 ms |
33408 KB |
Output is correct |
| 6 |
Correct |
24 ms |
33400 KB |
Output is correct |
| 7 |
Correct |
19 ms |
33144 KB |
Output is correct |
| 8 |
Correct |
346 ms |
46840 KB |
Output is correct |
| 9 |
Correct |
216 ms |
40444 KB |
Output is correct |
| 10 |
Correct |
550 ms |
51320 KB |
Output is correct |
| 11 |
Correct |
360 ms |
52220 KB |
Output is correct |
| 12 |
Correct |
351 ms |
50680 KB |
Output is correct |
| 13 |
Correct |
19 ms |
33152 KB |
Output is correct |
| 14 |
Correct |
340 ms |
46840 KB |
Output is correct |
| 15 |
Correct |
57 ms |
34296 KB |
Output is correct |
| 16 |
Correct |
657 ms |
51448 KB |
Output is correct |
| 17 |
Correct |
368 ms |
50936 KB |
Output is correct |
| 18 |
Correct |
362 ms |
50936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
33152 KB |
Output is correct |
| 2 |
Correct |
24 ms |
33280 KB |
Output is correct |
| 3 |
Correct |
24 ms |
33272 KB |
Output is correct |
| 4 |
Correct |
29 ms |
33408 KB |
Output is correct |
| 5 |
Correct |
27 ms |
33408 KB |
Output is correct |
| 6 |
Correct |
27 ms |
33404 KB |
Output is correct |
| 7 |
Correct |
21 ms |
33152 KB |
Output is correct |
| 8 |
Correct |
332 ms |
46840 KB |
Output is correct |
| 9 |
Correct |
225 ms |
40472 KB |
Output is correct |
| 10 |
Correct |
547 ms |
51192 KB |
Output is correct |
| 11 |
Correct |
369 ms |
52344 KB |
Output is correct |
| 12 |
Correct |
363 ms |
50808 KB |
Output is correct |
| 13 |
Correct |
21 ms |
33152 KB |
Output is correct |
| 14 |
Correct |
340 ms |
46748 KB |
Output is correct |
| 15 |
Correct |
59 ms |
34296 KB |
Output is correct |
| 16 |
Correct |
656 ms |
51576 KB |
Output is correct |
| 17 |
Correct |
373 ms |
50936 KB |
Output is correct |
| 18 |
Correct |
367 ms |
50936 KB |
Output is correct |
| 19 |
Correct |
808 ms |
69624 KB |
Output is correct |
| 20 |
Correct |
799 ms |
67288 KB |
Output is correct |
| 21 |
Correct |
799 ms |
69628 KB |
Output is correct |
| 22 |
Correct |
804 ms |
67192 KB |
Output is correct |
| 23 |
Correct |
801 ms |
67196 KB |
Output is correct |
| 24 |
Correct |
803 ms |
67100 KB |
Output is correct |
| 25 |
Correct |
803 ms |
67192 KB |
Output is correct |
| 26 |
Correct |
801 ms |
69624 KB |
Output is correct |
| 27 |
Correct |
816 ms |
69624 KB |
Output is correct |
| 28 |
Correct |
795 ms |
67064 KB |
Output is correct |
| 29 |
Correct |
805 ms |
67108 KB |
Output is correct |
| 30 |
Correct |
802 ms |
67072 KB |
Output is correct |
