제출 #477536

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
477536		CyberSleeper	벽 (IOI14_wall)	C++17	100 / 100	1488 ms	161916 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

const int MX=2000007, INF=1e9+7;

int N;

struct SegTree{
    #define mi      (le+ri)/2
    #define idxl    (idx*2+1)
    #define idxr    (idx*2+2)

    struct Node{
        int mn, mx, lzmn, lzmx;
        Node(){
            mx=mn=lzmn=0;
            lzmx=INF;
        }
    }id;
    Node combin(Node a, Node b){
        Node ret;
        ret.mn=min(a.mn, b.mn);
        ret.mx=max(a.mx, b.mx);
        return ret;
    }

    Node ST[4*MX];
    int letar, ritar, val, ch;

    void prop(int idx, int le, int ri){
        if(ST[idx].lzmn){
            ST[idx].mn=max(ST[idx].lzmn, ST[idx].mn);
            ST[idx].mx=max(ST[idx].mn, ST[idx].mx);
            if(le<ri){
                ST[idxl].lzmn=max(ST[idxl].lzmn, ST[idx].lzmn);
                ST[idxl].lzmx=max(ST[idxl].lzmx, ST[idxl].lzmn);
                ST[idxr].lzmn=max(ST[idxr].lzmn, ST[idx].lzmn);
                ST[idxr].lzmx=max(ST[idxr].lzmx, ST[idxr].lzmn);
            }
        }
        if(ST[idx].lzmx!=INF){
            ST[idx].mx=min(ST[idx].lzmx, ST[idx].mx);
            ST[idx].mn=min(ST[idx].mx, ST[idx].mn);
            if(le<ri){
                ST[idxl].lzmx=min(ST[idxl].lzmx, ST[idx].lzmx);
                ST[idxl].lzmn=min(ST[idxl].lzmn, ST[idxl].lzmx);
                ST[idxr].lzmx=min(ST[idxr].lzmx, ST[idx].lzmx);
                ST[idxr].lzmn=min(ST[idxr].lzmn, ST[idxr].lzmx);
            }
        }
        ST[idx].lzmn=0;
        ST[idx].lzmx=INF;
    }
    void upd(int idx, int le, int ri){
        prop(idx, le, ri);
        if(ri<letar || ritar<le)
            return;
        if(letar<=le && ri<=ritar){
            if(ch&1){
                ST[idx].lzmn=max(ST[idx].lzmn, val);
                ST[idx].lzmx=max(ST[idx].lzmx, ST[idx].lzmn);
            }else{
                ST[idx].lzmx=min(ST[idx].lzmx, val);
                ST[idx].lzmn=min(ST[idx].lzmn, ST[idx].lzmx);
            }
            prop(idx, le, ri);
            return;
        }
        upd(idxl, le, mi); upd(idxr, mi+1, ri);
        ST[idx]=combin(ST[idxl], ST[idxr]);
    }
    int que(int idx, int le, int ri){
        prop(idx, le, ri);
        if(ri<letar || ritar<le)
            return 0;
        if(letar<=le && ri<=ritar){
            return ST[idx].mn;
        }
        return max(que(idxl, le, mi), que(idxr, mi+1, ri));
    }

    void update(int op, int le, int ri, int v){
        ch=op, letar=le, ritar=ri, val=v;
        upd(0, 0, N-1);
    }
    int query(int x){
        letar=ritar=x;
        return que(0, 0, N-1);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    N=n;
    SegTree ST;
    for(int i=0, ch, l, r, h; i<k; i++){
        ch=op[i], l=left[i], r=right[i], h=height[i];
        ST.update(ch, l, r, h);
    }
    for(int i=0; i<N; i++)
        finalHeight[i]=ST.query(i);
    return;
}

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