Submission #577554

#	Time	Username	Problem	Language	Result	Execution time	Memory
577554		Mazaalai	Wall (IOI14_wall)	C++17	100 / 100	828 ms	182900 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
const int M = 4*N;
const int MIN = 0, MAX = 1e5;
struct Node {
    int minVal, maxVal, lazyMin, lazyMax;
    bool isAdd;
    Node() {
        isAdd = 0;
        lazyMin = MIN;
        lazyMax = MAX;
        minVal = maxVal = 0;
    }
    Node(int a, int b, int c, int d, bool e) {
        minVal = a;
        maxVal = b;
        lazyMin = c;
        lazyMax = d;
        isAdd = e;
    }
};
Node node[M];

void propagate(int head) {
    if (node[head].lazyMin == MIN && node[head].lazyMax == MAX) return;
    int x = node[head].lazyMin; node[head].lazyMin = MIN;
    int y = node[head].lazyMax; node[head].lazyMax = MAX;
    for (int add = 1; add <= 2; add++) {
        node[head*2+add].minVal = max(node[head*2+add].minVal, x);
        node[head*2+add].lazyMin = max(node[head*2+add].lazyMin, x);
        if (x > node[head*2+add].maxVal) {
            node[head*2+add].maxVal = x;
            node[head*2+add].lazyMax = x;
        }
    }
    for (int add = 1; add <= 2; add++) {
        node[head*2+add].maxVal = min(node[head*2+add].maxVal, y);
        node[head*2+add].lazyMax = min(node[head*2+add].lazyMax, y);
        if (y < node[head*2+add].minVal) {
            node[head*2+add].minVal = y;
            node[head*2+add].lazyMin = y;
        }
    }
}
void update(int l, int r, int L, int R, int val, bool isAdd, int head) {
    if (l > R || L > r) return;
    if (isAdd && node[head].minVal >= val) return;
    if (!isAdd && node[head].maxVal <= val) return;
    if (L <= l && r <= R) {
        // cout << "UPDATE: " << l << ' ' << r << '\n';
        if (isAdd) {
            node[head].minVal = max(node[head].minVal, val);
            node[head].lazyMin = max(node[head].lazyMin, val);
            if (val > node[head].maxVal) {
                node[head].maxVal = val;
                node[head].lazyMax = val;
            }
        } else {
            node[head].maxVal = min(node[head].maxVal, val);
            node[head].lazyMax = min(node[head].lazyMax, val);
            if (val < node[head].minVal) {
                node[head].minVal = val;
                node[head].lazyMin = val;
            }
        }
        return;
    }
    int mid = (l+r)>>1;
    propagate(head);
    update(l, mid, L, R, val, isAdd, head*2+1);
    update(mid+1, r, L, R, val, isAdd, head*2+2);
    node[head] = Node({
        min(node[head*2+1].minVal, node[head*2+2].minVal),
        max(node[head*2+1].maxVal, node[head*2+2].maxVal),
        MIN,
        MAX,
        0
    });
}
void dfs(int l, int r, int res[], int head) {
    // cout << l << "," << r << ": " << node[head].minVal << ',' << node[head].maxVal << '\n';
    if (l == r) {
        // cout << node[head].minVal << " ";
        res[l] = node[head].minVal;
        return;
    }
    propagate(head);
    int mid = (l+r)>>1;
    dfs(l, mid, res, head*2+1);
    dfs(mid+1, r, res, head*2+2);
    // if (head == 0) cout << "\n";
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int res[]) {
    for (int i = 0; i < k; i++) {
        // dfs(0, n-1, res, 0);
        update(0, n-1, l[i], r[i], h[i], op[i]==1, 0);
    }
    dfs(0, n-1, res, 0);
    return;
}

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