Submission #537627

#	Time	Username	Problem	Language	Result	Execution time	Memory
537627		happypotato	Wall (IOI14_wall)	C++17	100 / 100	710 ms	134864 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second

const int mxN = 2e6 + 1;
int seg[4 * mxN];
pii lazy[4 * mxN];
bool marked[4 * mxN];
int n;
pii merge(pii a, pii b) {
    if (min({a.ff, a.ss, b.ff, b.ss}) == -1 || max({a.ff, a.ss, b.ff, b.ss}) == 1e5 + 1) {
        a.ff = max(a.ff, b.ff);
        a.ss = min(a.ss, b.ss);
        if (a.ff > a.ss) {
            if (b.ff > a.ss) return {b.ff, b.ff};
            else if (b.ss < a.ff) return {b.ss, b.ss};
        }
        return a;
    }
    if (a.ss < b.ff) {
        return {b.ff, b.ff};
    } else if (b.ss < a.ff) {
        return {b.ss, b.ss};
    }
    a.ff = max(a.ff, b.ff);
    a.ss = min(a.ss, b.ss);
    if (a.ff > a.ss) {
        if (b.ff > a.ss) return {b.ff, b.ff};
        else if (b.ss < a.ff) return {b.ss, b.ss};
    }
    return a;
}
void pushdown(int idx) {
    if (marked[idx]) {
        seg[(idx << 1)] = max(seg[(idx << 1)], lazy[idx].ff);
        seg[(idx << 1)] = min(seg[(idx << 1)], lazy[idx].ss);
        seg[(idx << 1) + 1] = max(seg[(idx << 1) + 1], lazy[idx].ff);
        seg[(idx << 1) + 1] = min(seg[(idx << 1) + 1], lazy[idx].ss);
        lazy[(idx << 1)] = merge(lazy[(idx << 1)], lazy[idx]);
        lazy[(idx << 1) + 1] = merge(lazy[(idx << 1) + 1], lazy[idx]);
        lazy[idx] = {-1, 1e6 + 1};
        marked[(idx << 1)] = true;
        marked[(idx << 1) + 1] = true;
        marked[idx] = false;
    }
}
void update(int tl, int tr, bool ismin, int val, int l = 1, int r = n, int idx = 1) {
    if (l > r) return;
    if (tl <= l && r <= tr) {
        if (ismin) {
            seg[idx] = min(seg[idx], val);
            lazy[idx].ss = min(lazy[idx].ss, val);
            if (lazy[idx].ff > lazy[idx].ss) {
                lazy[idx].ff = lazy[idx].ss;
            }
        } else {
            seg[idx] = max(seg[idx], val);
            lazy[idx].ff = max(lazy[idx].ff, val);
            if (lazy[idx].ff > lazy[idx].ss) {
                lazy[idx].ss = lazy[idx].ff;
            }
        }
        marked[idx] = true;
        return;
    }
    pushdown(idx);
    int mid = (l + r) >> 1;
    if (tl <= mid) update(tl, min(tr, mid), ismin, val, l, mid, (idx << 1));
    if (tr > mid) update(max(tl, mid + 1), tr, ismin, val, mid + 1, r, (idx << 1) + 1);

    return;
}
int query(int tar, int l = 1, int r = n, int idx = 1) {
    if (l > r) return -1;
    if (l == r) return seg[idx];
    pushdown(idx);
    int mid = (l + r) >> 1;
    if (tar <= mid) return query(tar, l, mid, (idx << 1));
    else return query(tar, mid + 1, r, (idx << 1) + 1);
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    n = N;
    for (int i = 0; i < 4 * mxN; i++) {
        seg[i] = 0;
        lazy[i] = {-1, 1e6 + 1};
    }
    for (int i = 0; i < k; i++) {
        update(left[i] + 1, right[i] + 1, (op[i] == 2), height[i]);
    }
    for (int i = 0; i < n; i++) {
        finalHeight[i] = query(i + 1);
    }
    return;
}

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