Submission #995460

#	Time	Username	Problem	Language	Result	Execution time	Memory
995460		thinknoexit	Wall (IOI14_wall)	C++17	100 / 100	472 ms	69460 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2000001;
int mn[4 * N], mx[4 * N];
int n, k;
void upd(int MN, int MX, int now) {
    mn[now] = max(MN, min(mn[now], mx[now]));
    mx[now] = min(MX, max(mn[now], mx[now]));
}
void push(int now) {
    upd(mn[now], mx[now], 2 * now);
    upd(mn[now], mx[now], 2 * now + 1);
    mn[now] = 0, mx[now] = 1e9;
}
void build(int now = 1, int l = 1, int r = n) {
    mn[now] = 0;
    mx[now] = 1e9;
    if (l == r) return;
    int mid = (l + r) / 2;
    build(2 * now, l, mid);
    build(2 * now + 1, mid + 1, r);
}
void update(int ql, int qr, int w, int op, int now = 1, int l = 1, int r = n) {
    if (l > qr || r < ql) return;
    if (ql <= l && r <= qr) {
        if (op == 1) upd(w, 1e9, now);
        else upd(0, w, now);
        return;
    }
    push(now);
    int mid = (l + r) / 2;
    update(ql, qr, w, op, 2 * now, l, mid);
    update(ql, qr, w, op, 2 * now + 1, mid + 1, r);
}
void cal(int finalHeight[], int now = 1, int l = 1, int r = n) {
    if (l == r) {
        finalHeight[l - 1] = min(mn[now], mx[now]);
        return;
    }
    push(now);
    int mid = (l + r) / 2;
    cal(finalHeight, 2 * now, l, mid);
    cal(finalHeight, 2 * now + 1, mid + 1, r);
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
    n = N, k = K;
    build();
    for (int i = 0;i < k;i++) {
        update(left[i] + 1, right[i] + 1, height[i], op[i]);
        // cal(finalHeight);
        // for (int i = 0;i < n;i++) {
        //     cout << finalHeight[i] << ' ';
        // }
        // cout << '\n';
    }
    cal(finalHeight);
}

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