| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 16749 |
2015-09-13T15:14:00 Z |
choyi0521 |
Wall (IOI14_wall) |
C++ |
|
2638 ms |
79224 KB |
#include "wall.h"
#include<algorithm>
using namespace std;
const int MAX_N=2000000;
struct st{
int mini,maxi;
st():mini(0),maxi(0x7fffffff){}
}tree[MAX_N*4];
int *final;
void update(int now,int l,int r,int gl,int gr,int mini,int maxi){
if(r<gl||gr<l) return;
if(gl<=l&&r<=gr){
tree[now].mini=min(maxi,max(tree[now].mini,mini));
tree[now].maxi=max(mini,min(tree[now].maxi,maxi));
if(l==r) final[l]=tree[now].mini;
return;
}
int m=(l+r)/2;
update(now*2+1,l,m,l,m,tree[now].mini,tree[now].maxi);
update(now*2+2,m+1,r,m+1,r,tree[now].mini,tree[now].maxi);
tree[now].mini=0; tree[now].maxi=0x7fffffff;
update(now*2+1,l,m,gl,gr,mini,maxi);
update(now*2+2,m+1,r,gl,gr,mini,maxi);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
final=finalHeight;
for(int i=0; i<k; i++)
update(0,0,n-1,left[i],right[i],
op[i]==1?height[i]:0,op[i]==2?height[i]:0x7fffffff);
for(int i=0; i<n; i++)
update(0,0,n-1,i,i,0,0x7fffffff);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
63584 KB |
Output is correct |
| 2 |
Correct |
5 ms |
63584 KB |
Output is correct |
| 3 |
Correct |
16 ms |
63584 KB |
Output is correct |
| 4 |
Correct |
24 ms |
63584 KB |
Output is correct |
| 5 |
Correct |
21 ms |
63584 KB |
Output is correct |
| 6 |
Correct |
27 ms |
63584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
63584 KB |
Output is correct |
| 2 |
Correct |
174 ms |
71408 KB |
Output is correct |
| 3 |
Correct |
362 ms |
66832 KB |
Output is correct |
| 4 |
Correct |
920 ms |
71800 KB |
Output is correct |
| 5 |
Correct |
585 ms |
71800 KB |
Output is correct |
| 6 |
Correct |
660 ms |
71800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
63584 KB |
Output is correct |
| 2 |
Correct |
12 ms |
63584 KB |
Output is correct |
| 3 |
Correct |
16 ms |
63584 KB |
Output is correct |
| 4 |
Correct |
28 ms |
63584 KB |
Output is correct |
| 5 |
Correct |
31 ms |
63584 KB |
Output is correct |
| 6 |
Correct |
13 ms |
63584 KB |
Output is correct |
| 7 |
Correct |
12 ms |
63584 KB |
Output is correct |
| 8 |
Correct |
153 ms |
71408 KB |
Output is correct |
| 9 |
Correct |
370 ms |
66832 KB |
Output is correct |
| 10 |
Correct |
918 ms |
71800 KB |
Output is correct |
| 11 |
Correct |
642 ms |
71800 KB |
Output is correct |
| 12 |
Correct |
614 ms |
71800 KB |
Output is correct |
| 13 |
Correct |
9 ms |
63584 KB |
Output is correct |
| 14 |
Correct |
161 ms |
71408 KB |
Output is correct |
| 15 |
Correct |
83 ms |
64068 KB |
Output is correct |
| 16 |
Correct |
1015 ms |
71800 KB |
Output is correct |
| 17 |
Correct |
594 ms |
71800 KB |
Output is correct |
| 18 |
Correct |
641 ms |
71800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
63584 KB |
Output is correct |
| 2 |
Correct |
5 ms |
63584 KB |
Output is correct |
| 3 |
Correct |
0 ms |
63584 KB |
Output is correct |
| 4 |
Correct |
29 ms |
63584 KB |
Output is correct |
| 5 |
Correct |
13 ms |
63584 KB |
Output is correct |
| 6 |
Correct |
22 ms |
63584 KB |
Output is correct |
| 7 |
Correct |
0 ms |
63584 KB |
Output is correct |
| 8 |
Correct |
192 ms |
71408 KB |
Output is correct |
| 9 |
Correct |
344 ms |
66832 KB |
Output is correct |
| 10 |
Correct |
908 ms |
71800 KB |
Output is correct |
| 11 |
Correct |
589 ms |
71800 KB |
Output is correct |
| 12 |
Correct |
570 ms |
71800 KB |
Output is correct |
| 13 |
Correct |
7 ms |
63584 KB |
Output is correct |
| 14 |
Correct |
90 ms |
71408 KB |
Output is correct |
| 15 |
Correct |
65 ms |
64068 KB |
Output is correct |
| 16 |
Correct |
1032 ms |
71800 KB |
Output is correct |
| 17 |
Correct |
618 ms |
71800 KB |
Output is correct |
| 18 |
Correct |
616 ms |
71800 KB |
Output is correct |
| 19 |
Correct |
2616 ms |
79224 KB |
Output is correct |
| 20 |
Correct |
2576 ms |
79224 KB |
Output is correct |
| 21 |
Correct |
2575 ms |
79224 KB |
Output is correct |
| 22 |
Correct |
2598 ms |
79224 KB |
Output is correct |
| 23 |
Correct |
2638 ms |
79224 KB |
Output is correct |
| 24 |
Correct |
2605 ms |
79224 KB |
Output is correct |
| 25 |
Correct |
2572 ms |
79224 KB |
Output is correct |
| 26 |
Correct |
2612 ms |
79224 KB |
Output is correct |
| 27 |
Correct |
2559 ms |
79224 KB |
Output is correct |
| 28 |
Correct |
2595 ms |
79224 KB |
Output is correct |
| 29 |
Correct |
2578 ms |
79224 KB |
Output is correct |
| 30 |
Correct |
2581 ms |
79224 KB |
Output is correct |
