oj.uz

답안 #18617

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18617 2016-02-12T14:22:13 Z mindol 벽 (IOI14_wall) C++14
100 / 100
 1422 ms 49492 KB 
#include<algorithm>
using namespace std;

int lo[1<<22],hi[1<<22],base=1<<21;

void init()
{
    int sz=1<<22;
    for(int i=1;i<sz;i++)
        lo[i]=0, hi[i]=100000;
}

void down(int now)
{
    if(now>=base) return;
    hi[now*2]=min(max(hi[now*2],lo[now]),hi[now]);
    lo[now*2]=max(min(lo[now*2],hi[now]),lo[now]);
    hi[now*2+1]=min(max(hi[now*2+1],lo[now]),hi[now]);
    lo[now*2+1]=max(min(lo[now*2+1],hi[now]),lo[now]);
    lo[now]=0, hi[now]=100000;
}

void update(int l,int r,int type,int value,int now,int now_l,int now_r)
{
    down(now);
    if(now_r<l || now_l>r) return;
    else if(l<=now_l && now_r<=r)
    {
        if(type==0)
        {
            lo[now]=max(lo[now],value);
            hi[now]=max(hi[now],value);
        }
        else
        {
            hi[now]=min(hi[now],value);
            lo[now]=min(lo[now],value);
        }
        down(now);
    }
    else
    {
        int mid=(now_l+now_r)/2;
        update(l,r,type,value,now*2,now_l,mid);
        update(l,r,type,value,now*2+1,mid+1,now_r);
    }
}

void make_res(int now,int now_l,int now_r)
{
    down(now);
    if(now_l==now_r) return;
    int mid=(now_l+now_r)/2;
    make_res(now*2,now_l,mid);
    make_res(now*2+1,mid+1,now_r);
}

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
    init();
    for(int i=0;i<k;i++)
        update(left[i]+1,right[i]+1,op[i]-1,height[i],1,1,base);
    make_res(1,1,base);
    for(int i=0;i<n;i++)
        finalHeight[i]=lo[i+base];
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 33852 KB Output is correct
2 Correct 77 ms 33852 KB Output is correct
3 Correct 73 ms 33852 KB Output is correct
4 Correct 77 ms 33852 KB Output is correct
5 Correct 80 ms 33852 KB Output is correct
6 Correct 76 ms 33852 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 33852 KB Output is correct
2 Correct 727 ms 41676 KB Output is correct
3 Correct 453 ms 37100 KB Output is correct
4 Correct 1091 ms 42068 KB Output is correct
5 Correct 702 ms 42068 KB Output is correct
6 Correct 727 ms 42068 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 33852 KB Output is correct
2 Correct 78 ms 33852 KB Output is correct
3 Correct 74 ms 33852 KB Output is correct
4 Correct 76 ms 33852 KB Output is correct
5 Correct 76 ms 33852 KB Output is correct
6 Correct 80 ms 33852 KB Output is correct
7 Correct 67 ms 33852 KB Output is correct
8 Correct 764 ms 41676 KB Output is correct
9 Correct 457 ms 37100 KB Output is correct
10 Correct 1087 ms 42068 KB Output is correct
11 Correct 720 ms 42068 KB Output is correct
12 Correct 690 ms 42068 KB Output is correct
13 Correct 70 ms 33852 KB Output is correct
14 Correct 761 ms 41676 KB Output is correct
15 Correct 134 ms 34336 KB Output is correct
16 Correct 1134 ms 42068 KB Output is correct
17 Correct 722 ms 42068 KB Output is correct
18 Correct 732 ms 42068 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 33852 KB Output is correct
2 Correct 72 ms 33852 KB Output is correct
3 Correct 69 ms 33852 KB Output is correct
4 Correct 81 ms 33852 KB Output is correct
5 Correct 80 ms 33852 KB Output is correct
6 Correct 83 ms 33852 KB Output is correct
7 Correct 70 ms 33852 KB Output is correct
8 Correct 774 ms 41676 KB Output is correct
9 Correct 468 ms 37100 KB Output is correct
10 Correct 1084 ms 42068 KB Output is correct
11 Correct 722 ms 42068 KB Output is correct
12 Correct 732 ms 42068 KB Output is correct
13 Correct 70 ms 33852 KB Output is correct
14 Correct 759 ms 41676 KB Output is correct
15 Correct 124 ms 34336 KB Output is correct
16 Correct 1115 ms 42068 KB Output is correct
17 Correct 709 ms 42068 KB Output is correct
18 Correct 747 ms 42068 KB Output is correct
19 Correct 1369 ms 49492 KB Output is correct
20 Correct 1384 ms 49492 KB Output is correct
21 Correct 1369 ms 49492 KB Output is correct
22 Correct 1390 ms 49492 KB Output is correct
23 Correct 1344 ms 49492 KB Output is correct
24 Correct 1373 ms 49492 KB Output is correct
25 Correct 1317 ms 49492 KB Output is correct
26 Correct 1353 ms 49492 KB Output is correct
27 Correct 1381 ms 49492 KB Output is correct
28 Correct 1422 ms 49492 KB Output is correct
29 Correct 1398 ms 49492 KB Output is correct
30 Correct 1364 ms 49492 KB Output is correct