제출 #1211923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211923		dzhoz0	Wall (IOI14_wall)	C++20	100 / 100	549 ms	96816 KiB

wall

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

const int MAXN = 2e6;
struct Node {
    int l = 0, r = INT_MAX;
    Node() {}
    Node(int x): l(x), r(x) {}
    Node(int l, int r): l(l), r(r) {}
} st[4 * MAXN + 5];
int a[MAXN + 5];
Node intersect(Node a, Node b) {
    if(max(a.l, b.l) <= min(a.r, b.r)) return Node(max(a.l, b.l), min(a.r, b.r));
    else if(a.r < b.l) return Node(b.l);
    else return Node(b.r);
}

void down(int id, int l, int r) {
    if(l != r) {
        st[id * 2] = intersect(st[id * 2], st[id]);
        st[id * 2 + 1] = intersect(st[id * 2 + 1], st[id]);
        st[id] = Node();
    }
}

void upd(int id, int l, int r, int u, int v, Node x) {
    down(id, l, r);
    if(v < l || r < u) return;
    if(u <= l && r <= v) {
        st[id] = intersect(st[id], x);
        down(id, l, r);
        return;
    }
    int mid = (l + r) / 2;
    upd(id * 2, l, mid, u, v, x);
    upd(id * 2 + 1, mid + 1, r, u, v, x);
    st[id] = Node();
}

void build(int id, int l, int r) {
    down(id, l, r);
    if(l == r) a[l] = st[id].l;
    else {
        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i = 0; i < k; i++) {
        int t = op[i], l = left[i], r = right[i], h = height[i];
        l++, r++;
        upd(1, 1, n, l, r, (t == 1 ? Node(h, INT_MAX) : Node(0, h)));
    }
    build(1, 1, n);
    for(int i = 1; i <= n; i++) finalHeight[i - 1] = a[i];
    return;
}

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