oj.uz

Submission #18615

# Submission time Handle Problem Language Result Execution time Memory
18615 2016-02-12T13:41:10 Z mindol Wall (IOI14_wall) C++14
61 / 100
 2965 ms 262144 KB 
#include<algorithm>
#include<vector>
using namespace std;

struct Node{ int Max,Min; };
Node tree[1<<22]; // 구간의 최대, 최소

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(type==0) // 모든 값이 value 이상이 된다.
        {
            tree[now].Min=max(tree[now].Min,value);
            tree[now].Max=max(tree[now].Max,value);
        }
        else // 모든 값이 value 이하가 된다.
        {
            tree[now].Max=min(tree[now].Max,value);
            tree[now].Min=min(tree[now].Min,value);
        }

        if(now_l!=now_r)
        {
            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);
        tree[now].Max=max(tree[now*2].Max,tree[now*2+1].Max);
        tree[now].Min=max(tree[now*2].Min,tree[now*2+1].Min);
    }
}

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]=tree[base+i].Min;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 132284 KB Output is correct
2 Correct 78 ms 132284 KB Output is correct
3 Correct 78 ms 132284 KB Output is correct
4 Correct 92 ms 132944 KB Output is correct
5 Correct 78 ms 132944 KB Output is correct
6 Correct 79 ms 132944 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 132284 KB Output is correct
2 Correct 683 ms 140108 KB Output is correct
3 Correct 708 ms 136720 KB Output is correct
4 Correct 2098 ms 146704 KB Output is correct
5 Correct 764 ms 146704 KB Output is correct
6 Correct 736 ms 146704 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 132284 KB Output is correct
2 Correct 80 ms 132284 KB Output is correct
3 Correct 67 ms 132284 KB Output is correct
4 Correct 90 ms 132944 KB Output is correct
5 Correct 67 ms 132944 KB Output is correct
6 Correct 68 ms 132944 KB Output is correct
7 Correct 58 ms 132284 KB Output is correct
8 Correct 658 ms 140108 KB Output is correct
9 Correct 710 ms 136720 KB Output is correct
10 Correct 2145 ms 146704 KB Output is correct
11 Correct 746 ms 146704 KB Output is correct
12 Correct 746 ms 146704 KB Output is correct
13 Correct 64 ms 132284 KB Output is correct
14 Correct 679 ms 140108 KB Output is correct
15 Correct 203 ms 133824 KB Output is correct
16 Correct 2965 ms 146704 KB Output is correct
17 Correct 776 ms 146704 KB Output is correct
18 Correct 769 ms 146704 KB Output is correct

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 132284 KB Output is correct
2 Correct 64 ms 132284 KB Output is correct
3 Correct 70 ms 132284 KB Output is correct
4 Correct 93 ms 132944 KB Output is correct
5 Correct 76 ms 132944 KB Output is correct
6 Correct 76 ms 132944 KB Output is correct
7 Correct 64 ms 132284 KB Output is correct
8 Correct 721 ms 140108 KB Output is correct
9 Correct 690 ms 136720 KB Output is correct
10 Correct 2114 ms 146704 KB Output is correct
11 Correct 703 ms 146704 KB Output is correct
12 Correct 729 ms 146704 KB Output is correct
13 Correct 61 ms 132284 KB Output is correct
14 Correct 726 ms 140108 KB Output is correct
15 Correct 204 ms 133824 KB Output is correct
16 Correct 2895 ms 146704 KB Output is correct
17 Correct 753 ms 146704 KB Output is correct
18 Correct 763 ms 146704 KB Output is correct
19 Memory limit exceeded 1668 ms 262144 KB Memory limit exceeded
20 Halted 0 ms 0 KB -