제출 #113591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
113591		nvmdava	벽 (IOI14_wall)	C++17	100 / 100	784 ms	77764 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define N 2097152
#define inf 100005
struct Query{
    int l, r;
};

Query lazy[N << 1];
int tree[N << 1];

void push(int id){
    if(id >= N){
        tree[id] = min(tree[id], lazy[id].r);
        tree[id] = max(tree[id], lazy[id].l);
    } else {
        if(lazy[id << 1].r <= lazy[id].l){
            lazy[id << 1].l = lazy[id].l;
            lazy[id << 1].r = lazy[id].l;
        } else if(lazy[id << 1].l >= lazy[id].r){
            lazy[id << 1].l = lazy[id].r;
            lazy[id << 1].r = lazy[id].r;
        } else {
            lazy[id << 1].l = max(lazy[id << 1].l, lazy[id].l);
            lazy[id << 1].r = min(lazy[id << 1].r, lazy[id].r);
        }
        if(lazy[id << 1 | 1].r <= lazy[id].l){
            lazy[id << 1 | 1].l = lazy[id].l;
            lazy[id << 1 | 1].r = lazy[id].l;
        } else if(lazy[id << 1 | 1].l >= lazy[id].r){
            lazy[id << 1 | 1].l = lazy[id].r;
            lazy[id << 1 | 1].r = lazy[id].r;
        } else {
            lazy[id << 1 | 1].l = max(lazy[id << 1 | 1].l, lazy[id].l);
            lazy[id << 1 | 1].r = min(lazy[id << 1 | 1].r, lazy[id].r);
        }
    }
    lazy[id].l = 0;
    lazy[id].r = inf;
}

void update(int id, int l, int r, int L, int R, int vall, int valr){
    if(R < l || L > r) return;
    push(id);
    if(L <= l && r <= R){
        lazy[id].l = vall;
        lazy[id].r = valr;
    } else {
        int m = (l + r) >> 1;
        update(id << 1, l, m, L, R, vall, valr);
        update(id << 1 | 1, m + 1, r, L, R, vall ,valr);
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i = 0; i < k; i++){
        if(op[i] == 1)
            update(1, 1, N, left[i] + 1, right[i] + 1, height[i], inf);
        else
            update(1, 1, N, left[i] + 1, right[i] + 1, 0, height[i]);
    }
    for(int i = 1; i < N * 2; i++)
        push(i);
    for(int i = 0; i < n; i++){
        finalHeight[i] = tree[i + N];
    }
}

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