제출 #1294518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1294518		ChottuF	벽 (IOI14_wall)	C++20	100 / 100	394 ms	96816 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6+5;
const int INF = 1e9;
bool has_lazy[4*MAXN];


struct Node{
    int mn,mx;
    Node(){
        mn = 0;
        mx = INF;
    }
};
Node lazy[4*MAXN];

void push(int v, int tl, int tr){
    if (has_lazy[v]){
        int tm = (tl+tr)/2;
        lazy[2*v].mn = min(lazy[v].mx, max(lazy[v].mn, lazy[2*v].mn));
        lazy[2*v].mx = min(lazy[v].mx, max(lazy[v].mn, lazy[2*v].mx));

        lazy[2*v+1].mn = min(lazy[v].mx, max(lazy[v].mn, lazy[2*v+1].mn));
        lazy[2*v+1].mx = min(lazy[v].mx, max(lazy[v].mn, lazy[2*v+1].mx));
        
        has_lazy[v] = false;
        lazy[v] = Node();
        has_lazy[2*v] = true;
        has_lazy[2*v+1] = true;
    }
}

void update(int v, int tl, int tr, int l, int r, int constraint, bool type1){
    if (l > r) return;
    //type1 0 -> max
    //type1 1 -> mn
    
    if (!type1){
        if (l == tl && r == tr){
            lazy[v].mn = max(lazy[v].mn, constraint);
            lazy[v].mx = max(lazy[v].mx, constraint);
            has_lazy[v] = true;
        }
        else{
            push(v, tl, tr);
            int tm = (tl+tr)/2;
            update(2*v, tl, tm, l, min(r,tm), constraint, type1);
            update(2*v+1, tm+1, tr, max(l,tm+1), r, constraint, type1);
        }
    }
    else{
        if (l == tl && r == tr){
            lazy[v].mn = min(lazy[v].mn, constraint);
            lazy[v].mx = min(lazy[v].mx, constraint);
            has_lazy[v] = true;
        }
        else{
            push(v, tl, tr);
            int tm = (tl+tr)/2;
            update(2*v, tl, tm, l, min(r,tm), constraint, type1);
            update(2*v+1, tm+1, tr, max(l,tm+1), r, constraint, type1);
        }
    }
}


void build_final(int v, int tl, int tr, int finalHeight[]){
    if (tl == tr){
        finalHeight[tl] = lazy[v].mn;
        return;
    }
    push(v, tl, tr);
    int tm = (tl+tr)/2;
    build_final(2*v, tl, tm, finalHeight);
    build_final(2*v+1, tm+1, tr, finalHeight);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i<4*n; i++){
        lazy[i] = Node();
        has_lazy[i] = false;
    }
    
    for (int i = 0; i<k; i++){
        bool type1 = (op[i] == 2);
        update(1,0,n-1,left[i],right[i],height[i],type1);
    }
    build_final(1, 0, n-1, finalHeight);
    return;
}

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