제출 #202549

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
202549		DavidDamian	벽 (IOI14_wall)	C++11	32 / 100	3082 ms	21880 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int segm_tree[5000000];
int leftNode(int i)
{
    return i*2;
}
int rightNode(int i)
{
    return i*2+1;
}
void recompute(int i)
{
    segm_tree[i]=max(segm_tree[leftNode(i)],segm_tree[rightNode(i)]);
}
struct ura
{
    int type;
    int var1;
    int var2;
} lazy[5000000];
#define a 1 //Add
#define r 2 //Remove
#define c 3 //Change
#define b 4 //Bound
void propagate(int i,int L,int R)
{
    int mid=(L+R)/2;
    if(lazy[i].type==0) return;
    if(lazy[i].type==a) segm_tree[i]=max(segm_tree[i],lazy[i].var1);
    if(lazy[i].type==r) segm_tree[i]=min(segm_tree[i],lazy[i].var1);
    if(L<R){
        if(lazy[i].type!=lazy[leftNode(i)].type) {
            propagate(leftNode(i),L,mid);
            lazy[leftNode(i)]=lazy[i];
        }
        else{
            if(lazy[i].type==a){
                lazy[leftNode(i)].var1=max(lazy[leftNode(i)].var1,lazy[i].var1);
            }
            else{
                lazy[leftNode(i)].var1=min(lazy[leftNode(i)].var1,lazy[i].var1);
            }
        }
        if(lazy[i].type!=lazy[rightNode(i)].type) {
            propagate(rightNode(i),mid+1,R);
            lazy[rightNode(i)]=lazy[i];
        }
        else{
            if(lazy[i].type==a){
                lazy[rightNode(i)].var1=max(lazy[rightNode(i)].var1,lazy[i].var1);
            }
            else{
                lazy[rightNode(i)].var1=min(lazy[rightNode(i)].var1,lazy[i].var1);
            }
        }
    }
    lazy[i].type=0;
}
void update(int i,int L,int R,int x,int y,int type,int h)
{
    propagate(i,L,R);
    if(x<=L && R<=y)
        lazy[i].type=type,lazy[i].var1=h;
    else{
        int mid=(L+R)/2;
        if(x<=mid)
            update(leftNode(i),L,mid,x,y,type,h);
        if(mid+1<=y)
            update(rightNode(i),mid+1,R,x,y,type,h);
        propagate(leftNode(i),L,mid);
        propagate(rightNode(i),mid+1,R);
        recompute(i);
    }
}
int query(int i,int L,int R,int x)
{
    propagate(i,L,R);
    if(L==R){
        return segm_tree[i];
    }
    else{
        int mid=(L+R)/2;
        if(x<=mid)
            return query(leftNode(i),L,mid,x);
        else
            return query(rightNode(i),mid+1,R,x);
    }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    if(k<=5001){
        for(int i=0;i<k;i++){
            for(int j=left[i];j<=right[i];j++){
                if(op[i]==1){
                    finalHeight[j]=max(finalHeight[j],height[i]);
                }
                else{
                    finalHeight[j]=min(finalHeight[j],height[i]);
                }
            }
        }
        return;
    }
    for(int i=0;i<k;i++){
        update(1,1,n,left[i]+1,right[i]+1,op[i],height[i]);
    }
    for(int i=0;i<n;i++){
        finalHeight[i]=query(1,1,n,i+1);
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39