Submission #550831

#	Time	Username	Problem	Language	Result	Execution time	Memory
550831		Mazaalai	Wall (IOI14_wall)	C++17	100 / 100	818 ms	102388 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: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39