| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 16748 |
2015-09-13T14:37:37 Z |
choyi0521 |
Wall (IOI14_wall) |
C++ |
|
1625 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];
void update(int now,int l,int r,int gl,int gr,int op,int h){
if(r<gl||gr<l) return;
if(gl<=l&&r<=gr){
if(op==1){
tree[now].mini=max(tree[now].mini,h);
tree[now].maxi=max(tree[now].mini,tree[now].maxi);
}
else{
tree[now].maxi=min(tree[now].maxi,h);
tree[now].mini=min(tree[now].mini,tree[now].maxi);
}
return;
}
tree[now*2+1].mini=max(tree[now].mini,min(tree[now].maxi,tree[now*2+1].mini));
tree[now*2+1].maxi=min(tree[now].maxi,max(tree[now].mini,tree[now*2+1].maxi));
tree[now*2+2].mini=max(tree[now].mini,min(tree[now].maxi,tree[now*2+2].mini));
tree[now*2+2].maxi=min(tree[now].maxi,max(tree[now].mini,tree[now*2+2].maxi));
tree[now].mini=0;
tree[now].maxi=0x7fffffff;
update(now*2+1,l,(l+r)/2,gl,gr,op,h);
update(now*2+2,(l+r)/2+1,r,gl,gr,op,h);
}
int f(int now,int l,int r,int g){
if(r<g||g<l) return 0;
if(l==r) return tree[now].mini;
tree[now*2+1].mini=max(tree[now].mini,min(tree[now].maxi,tree[now*2+1].mini));
tree[now*2+1].maxi=min(tree[now].maxi,max(tree[now].mini,tree[now*2+1].maxi));
tree[now*2+2].mini=max(tree[now].mini,min(tree[now].maxi,tree[now*2+2].mini));
tree[now*2+2].maxi=min(tree[now].maxi,max(tree[now].mini,tree[now*2+2].maxi));
tree[now].mini=0;
tree[now].maxi=0x7fffffff;
return max(f(now*2+1,l,(l+r)/2,g),f(now*2+2,(l+r)/2+1,r,g));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0; i<k; i++)
update(0,0,n-1,left[i],right[i],op[i],height[i]);
for(int i=0; i<n; i++)
finalHeight[i]=f(0,0,n-1,i);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
63584 KB |
Output is correct |
| 2 |
Correct |
13 ms |
63584 KB |
Output is correct |
| 3 |
Correct |
10 ms |
63584 KB |
Output is correct |
| 4 |
Correct |
19 ms |
63584 KB |
Output is correct |
| 5 |
Correct |
11 ms |
63584 KB |
Output is correct |
| 6 |
Correct |
28 ms |
63584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
63584 KB |
Output is correct |
| 2 |
Correct |
76 ms |
71408 KB |
Output is correct |
| 3 |
Correct |
253 ms |
66832 KB |
Output is correct |
| 4 |
Correct |
634 ms |
71800 KB |
Output is correct |
| 5 |
Correct |
419 ms |
71800 KB |
Output is correct |
| 6 |
Correct |
428 ms |
71800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
63584 KB |
Output is correct |
| 2 |
Correct |
17 ms |
63584 KB |
Output is correct |
| 3 |
Correct |
10 ms |
63584 KB |
Output is correct |
| 4 |
Correct |
29 ms |
63584 KB |
Output is correct |
| 5 |
Correct |
12 ms |
63584 KB |
Output is correct |
| 6 |
Correct |
17 ms |
63584 KB |
Output is correct |
| 7 |
Correct |
3 ms |
63584 KB |
Output is correct |
| 8 |
Correct |
166 ms |
71408 KB |
Output is correct |
| 9 |
Correct |
212 ms |
66832 KB |
Output is correct |
| 10 |
Correct |
618 ms |
71800 KB |
Output is correct |
| 11 |
Correct |
426 ms |
71800 KB |
Output is correct |
| 12 |
Correct |
416 ms |
71800 KB |
Output is correct |
| 13 |
Correct |
0 ms |
63584 KB |
Output is correct |
| 14 |
Correct |
191 ms |
71408 KB |
Output is correct |
| 15 |
Correct |
51 ms |
64068 KB |
Output is correct |
| 16 |
Correct |
718 ms |
71800 KB |
Output is correct |
| 17 |
Correct |
497 ms |
71800 KB |
Output is correct |
| 18 |
Correct |
423 ms |
71800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
63584 KB |
Output is correct |
| 2 |
Correct |
8 ms |
63584 KB |
Output is correct |
| 3 |
Correct |
20 ms |
63584 KB |
Output is correct |
| 4 |
Correct |
10 ms |
63584 KB |
Output is correct |
| 5 |
Correct |
23 ms |
63584 KB |
Output is correct |
| 6 |
Correct |
23 ms |
63584 KB |
Output is correct |
| 7 |
Correct |
0 ms |
63584 KB |
Output is correct |
| 8 |
Correct |
144 ms |
71408 KB |
Output is correct |
| 9 |
Correct |
235 ms |
66832 KB |
Output is correct |
| 10 |
Correct |
630 ms |
71800 KB |
Output is correct |
| 11 |
Correct |
504 ms |
71800 KB |
Output is correct |
| 12 |
Correct |
436 ms |
71800 KB |
Output is correct |
| 13 |
Correct |
11 ms |
63584 KB |
Output is correct |
| 14 |
Correct |
203 ms |
71408 KB |
Output is correct |
| 15 |
Correct |
63 ms |
64068 KB |
Output is correct |
| 16 |
Correct |
667 ms |
71800 KB |
Output is correct |
| 17 |
Correct |
499 ms |
71800 KB |
Output is correct |
| 18 |
Correct |
474 ms |
71800 KB |
Output is correct |
| 19 |
Correct |
1549 ms |
79224 KB |
Output is correct |
| 20 |
Correct |
1509 ms |
79224 KB |
Output is correct |
| 21 |
Correct |
1625 ms |
79224 KB |
Output is correct |
| 22 |
Correct |
1599 ms |
79224 KB |
Output is correct |
| 23 |
Correct |
1571 ms |
79224 KB |
Output is correct |
| 24 |
Correct |
1360 ms |
79224 KB |
Output is correct |
| 25 |
Correct |
1579 ms |
79224 KB |
Output is correct |
| 26 |
Correct |
1558 ms |
79224 KB |
Output is correct |
| 27 |
Correct |
1558 ms |
79224 KB |
Output is correct |
| 28 |
Correct |
1568 ms |
79224 KB |
Output is correct |
| 29 |
Correct |
1572 ms |
79224 KB |
Output is correct |
| 30 |
Correct |
1547 ms |
79224 KB |
Output is correct |
