제출 #1266645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266645		avohado	Wall (IOI14_wall)	C++20	0 / 100	98 ms	8264 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const long maxn=2e6+5;
int tree[maxn*2], mint[maxn*2], maxt[maxn*2], push[maxn*2], a[maxn];
void get(int v, int l, int r, int tl, int tr, int h, int op){
    if(push[v]!=-1){
        mint[v]=maxt[v]=push[v];
        if(tl!=tr){
            push[v*2]=push[v*2+1]=push[v];
        }
        push[v]=-1;
    }
    if(tl>r||l>tr){
        return;
    }
    if(tl>=l&&tr<=r){
        if(op==1&&maxt[v]<h||op==2&&mint[v]>h){
            mint[v]=maxt[v]=h;
            if(tl!=tr){
                push[v*2]=push[v*2+1]=h;
            }
            return;
        }else if(op==1&&mint[v]>=h||op==2&&maxt[v]<=h){
            return;
        }
    }
    int tm=(tl+tr)/2;
    get(v*2, l, r, tl, tm, h, op);
    get(v*2+1, l, r, tm+1, tr, h, op);
    mint[v]=min(mint[v*2], mint[v*2+1]);
    maxt[v]=max(maxt[v*2], maxt[v*2+1]);
}
void bt(int v, int tl, int tr){
    if(tl==tr){
        a[tl]=mint[v];
        return;
    }
    int tm=(tl+tr)/2;
    bt(v*2, tl, tm);
    bt(v*2+1, tm+1, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i=0; i<k; i++){
        get(1, left[i], right[i], 0, n-1, height[i], op[i]);
    }
    bt(1, 0, n-1);
    for(int i=0; i<n; i++){
        finalHeight[i]=a[i];
    }
    return;
}

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