제출 #550830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550830		Mazaalai	벽 (IOI14_wall)	C++17	8 / 100	3067 ms	79644 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
const int M = 4.2e6;
bool setMax = 1;
struct Node {
    int mini, maxi, lazyMin, lazyMax;
    Node() : mini(0), maxi(0), lazyMin(-1), lazyMax(-1) {};
    void setMinMax(int _mini, int _maxi) {
        mini = _mini;
        maxi = _maxi;
    }
    void mergeLazy(int val, bool type) {
        if (val == -1) return;
        if (type == setMax) {
            lazyMax = min((lazyMax == -1 ? val : lazyMax), val);
            maxi = min(maxi, lazyMax);
            if (maxi < mini) {
                mini = maxi;
                lazyMin = lazyMax;
            }
        } else {
            lazyMin = max((lazyMin == -1 ? val : lazyMin), val);
            mini = max(mini, lazyMin);
            if (maxi < mini) {
                maxi = mini;
                lazyMax = lazyMin;
            }
        }
    }
} node[M];
void propagate(int head) {
    if (node[head].lazyMin == -1 && node[head].lazyMax == -1) return;
    int lazyMin = node[head].lazyMin; node[head].lazyMin = -1;
    int lazyMax = node[head].lazyMax; node[head].lazyMax = -1;
    node[head*2+1].mergeLazy(lazyMin, 0);
    node[head*2+1].mergeLazy(lazyMax, 1);
    node[head*2+2].mergeLazy(lazyMin, 0);
    node[head*2+2].mergeLazy(lazyMax, 1);
}
void update(int l, int r, int L, int R, int val, bool isSetMax, int head) {
    if (l > R || L > r) return;
    if ((isSetMax && node[head].maxi <= val) || 
        (!isSetMax && node[head].mini >= val)) {
        return;
    }
    if (L <= l && r <= R) {
        node[head].mergeLazy(val, isSetMax);
        return;
    }
    int mid = (l+r)>>1;
    propagate(head);
    update(l, mid, L, R, val, isSetMax, head*2+1);
    update(mid+1, r, L, R, val, isSetMax, head*2+2);
    node[head].setMinMax(
        min(node[head*2+1].mini, node[head*2+2].mini),
        max(node[head*2+1].maxi, node[head*2+2].maxi)
    );
}
void dfs(int l, int r, int res[], int head) {
    if (l == r) {
        res[l] = node[head].mini;
        return;
    }
    int mid = (l+r)>>1;
    propagate(head);
    dfs(l, mid, res, head*2+1);
    dfs(mid+1, r, res, head*2+2);
}
void buildWall(int n, int k, int t[], int L[], int R[], int H[], int res[]){
    int ADD = 1;
    n--;
    for (int i = 0; i < k; i++) {
        // cout << "----------------\n";
        if (t[i] == ADD) { // Add, setMin
            // cout << "UPDATE: " << L[i] << "," << R[i] << " " << H[i] << " type:  0\n";
            update(0, n, L[i], R[i], H[i], 0, 0);
        } else { // REMOVE, setMax
            // cout << "UPDATE: " << L[i] << "," << R[i] << " " << H[i] << " type:  1\n";
            update(0, n, L[i], R[i], H[i], 1, 0);
        }
        dfs(0, n, res, 0);
        // for (int i = 0; i <= n; i++) cout << res[i] << " \n"[i==n];
    }
    // cout << "=====================\n";
    dfs(0, n, res, 0);
    return;
}

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