oj.uz

Submission #18616

# Submission time Handle Problem Language Result Execution time Memory
18616 2016-02-12T13:46:23 Z mindol Wall (IOI14_wall) C++14
100 / 100
 2597 ms 248220 KB 
#include<algorithm>
#include<vector>
using namespace std;

int res[1<<21];

struct Lazy{ int type,value; };
vector<Lazy> lazy[1<<22]; // type이 0이면 하한, 1이면 상한 설정.
int base=1<<21;

void check(int type,int value,int now)
{
    if(lazy[now].size()==0) lazy[now].push_back({type,value});
    else if(lazy[now].size()==1)
    {
        if(lazy[now][0].type==type)
        {
            if(lazy[now][0].type==0) lazy[now][0].value=max(lazy[now][0].value,value);
            else lazy[now][0].value=min(lazy[now][0].value,value);
        }
        else lazy[now].push_back({type,value});
    }
    else
    {
        if(lazy[now][0].type==0) // lazy[now][1].type은 1이다.
        {
            if(type==1) lazy[now][1].value=min(lazy[now][1].value,value);
            else
            {
                if(value >= lazy[now][0].value) lazy[now][0]=lazy[now][1], lazy[now][1]={type,value};
                else if(value >= lazy[now][1].value) lazy[now][0]=lazy[now][1], lazy[now][1]={type,value};
            }
        }
        else // lazy[now][0].type은 1, lazy[now][1].type은 0이다.
        {
            if(type==0) lazy[now][1].value=max(lazy[now][1].value,value);
            else
            {
                if(value <= lazy[now][0].value) lazy[now][0]=lazy[now][1], lazy[now][1]={type,value};
                else if(value <= lazy[now][1].value) lazy[now][0]=lazy[now][1], lazy[now][1]={type,value};
            }
        }
    }
}

void lazydown(int now,int now_l,int now_r)
{
    for(int i=0;i<lazy[now].size();i++)
    {
        int type=lazy[now][i].type, value=lazy[now][i].value;
        if(now_l == now_r)
        {
            int index = now-base+1;
            if(type==0) res[index]=max(res[index],value);
            else res[index]=min(res[index],value);
        }
        else
        {
            check(type,value,now*2);
            check(type,value,now*2+1);
        }
    }
    lazy[now].clear();
}

void update(int l,int r,int type,int value,int now,int now_l,int now_r)
{
    lazydown(now,now_l,now_r);
    if(now_l>r || now_r<l) return;
    else if(l<=now_l && now_r<=r)
    {
        check(type,value,now);
        lazydown(now,now_l,now_r);
    }
    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)
{
    lazydown(now,now_l,now_r);
    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[])
{
    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]=res[i+1];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 107708 KB Output is correct
2 Correct 72 ms 107708 KB Output is correct
3 Correct 69 ms 107708 KB Output is correct
4 Correct 84 ms 108368 KB Output is correct
5 Correct 78 ms 108368 KB Output is correct
6 Correct 74 ms 108368 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 107708 KB Output is correct
2 Correct 574 ms 115532 KB Output is correct
3 Correct 622 ms 112144 KB Output is correct
4 Correct 1849 ms 122128 KB Output is correct
5 Correct 623 ms 122128 KB Output is correct
6 Correct 624 ms 122128 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 107708 KB Output is correct
2 Correct 63 ms 107708 KB Output is correct
3 Correct 78 ms 107708 KB Output is correct
4 Correct 84 ms 108368 KB Output is correct
5 Correct 81 ms 108368 KB Output is correct
6 Correct 83 ms 108368 KB Output is correct
7 Correct 69 ms 107708 KB Output is correct
8 Correct 552 ms 115532 KB Output is correct
9 Correct 613 ms 112144 KB Output is correct
10 Correct 1852 ms 122128 KB Output is correct
11 Correct 600 ms 122128 KB Output is correct
12 Correct 606 ms 122128 KB Output is correct
13 Correct 59 ms 107708 KB Output is correct
14 Correct 579 ms 115532 KB Output is correct
15 Correct 190 ms 109248 KB Output is correct
16 Correct 2584 ms 122128 KB Output is correct
17 Correct 638 ms 122128 KB Output is correct
18 Correct 628 ms 122128 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 107708 KB Output is correct
2 Correct 67 ms 107708 KB Output is correct
3 Correct 66 ms 107708 KB Output is correct
4 Correct 82 ms 108368 KB Output is correct
5 Correct 78 ms 108368 KB Output is correct
6 Correct 75 ms 108368 KB Output is correct
7 Correct 75 ms 107708 KB Output is correct
8 Correct 564 ms 115532 KB Output is correct
9 Correct 614 ms 112144 KB Output is correct
10 Correct 1847 ms 122128 KB Output is correct
11 Correct 635 ms 122128 KB Output is correct
12 Correct 608 ms 122128 KB Output is correct
13 Correct 61 ms 107708 KB Output is correct
14 Correct 550 ms 115532 KB Output is correct
15 Correct 193 ms 109248 KB Output is correct
16 Correct 2597 ms 122128 KB Output is correct
17 Correct 641 ms 122128 KB Output is correct
18 Correct 624 ms 122128 KB Output is correct
19 Correct 1929 ms 248220 KB Output is correct
20 Correct 1941 ms 248220 KB Output is correct
21 Correct 1930 ms 248220 KB Output is correct
22 Correct 1916 ms 248220 KB Output is correct
23 Correct 1910 ms 248220 KB Output is correct
24 Correct 1911 ms 248220 KB Output is correct
25 Correct 1931 ms 248220 KB Output is correct
26 Correct 1923 ms 248220 KB Output is correct
27 Correct 1900 ms 248220 KB Output is correct
28 Correct 1976 ms 248220 KB Output is correct
29 Correct 1924 ms 248220 KB Output is correct
30 Correct 1934 ms 248220 KB Output is correct