제출 #588252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
588252		AlperenT	벽 (IOI14_wall)	C++17	100 / 100	621 ms	91600 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

const int N = 2e6 + 5;

int n;

struct SegTree{
    int mn[N * 4], mx[N * 4];

    SegTree(){
        memset(mn, -1, sizeof(mn));
        memset(mx, -1, sizeof(mx));
    }

    void push(int v){
        if(mn[v] != -1){
            if(v * 2 < N * 4){
                if(mn[v * 2] == -1) mn[v * 2] = mn[v];
                else mn[v * 2] = max(mn[v * 2], mn[v]);

                if(mx[v * 2] != -1) mx[v * 2] = max(mx[v * 2], mn[v]);

                if(mn[v * 2 + 1] == -1) mn[v * 2 + 1] = mn[v];
                else mn[v * 2 + 1] = max(mn[v * 2 + 1], mn[v]);

                if(mx[v * 2 + 1] != -1) mx[v * 2 + 1] = max(mx[v * 2 + 1], mn[v]);
            }

            mn[v] = -1;
        }

        if(mx[v] != -1){
            if(v * 2 < N * 4){
                if(mx[v * 2] == -1) mx[v * 2] = mx[v];
                else mx[v * 2] = min(mx[v * 2], mx[v]);

                if(mn[v * 2] != -1) mn[v * 2] = min(mn[v * 2], mx[v]);

                if(mx[v * 2 + 1] == -1) mx[v * 2 + 1] = mx[v];
                else mx[v * 2 + 1] = min(mx[v * 2 + 1], mx[v]);

                if(mn[v * 2 + 1] != -1) mn[v * 2 + 1] = min(mn[v * 2 + 1], mx[v]);
            }

            mx[v] = -1;
        }
    }

    void updatemin(int l, int r, int val, int v = 1, int tl = 0, int tr = n - 1){
        if(l > r) return;
        else if(l == tl && r == tr){
            if(mn[v] == -1) mn[v] = val;
            else{
                mn[v] = max(mn[v], val);
            }

            if(mx[v] != -1) mx[v] = max(mx[v], val);
        }
        else{
            push(v);

            int tm = tl + (tr - tl) / 2;

            updatemin(l, min(tm, r), val, v * 2, tl, tm);
            updatemin(max(tm + 1, l), r, val, v * 2 + 1, tm + 1, tr);
        }
    }

    void updatemax(int l, int r, int val, int v = 1, int tl = 0, int tr = n - 1){
        if(l > r) return;
        else if(l == tl && r == tr){
            if(mx[v] == -1) mx[v] = val;
            else{
                mx[v] = min(mx[v], val);
            }

            if(mn[v] != -1) mn[v] = min(mn[v], val);
        }
        else{
            push(v);

            int tm = tl + (tr - tl) / 2;

            updatemax(l, min(tm, r), val, v * 2, tl, tm);
            updatemax(max(tm + 1, l), r, val, v * 2 + 1, tm + 1, tr);
        }
    }

    void findarr(int *arr, int v = 1, int l = 0, int r = n - 1){
        if(l == r) arr[l] = max(mn[v], 0);
        else{
            push(v);

            int m = l + (r - l) / 2;

            findarr(arr, v * 2, l, m);
            findarr(arr, v * 2 + 1, m + 1, r);
        }
    }
};

SegTree sgt;

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    n = N;

    for(int i = 0; i < k; i++){
        if(op[i] == 1) sgt.updatemin(left[i], right[i], height[i]);
        else if(op[i] == 2) sgt.updatemax(left[i], right[i], height[i]);
    }

    sgt.findarr(finalHeight);
}

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