Submission #1139101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139101		Moonn	Wall (IOI14_wall)	C++20	0 / 100	157 ms	78592 KiB

wall

#include <bits/stdc++.h>
#define ll int
#define AI ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define oo 1e18
using namespace std;

const int sz = 2e6;
struct node {
    ll lzmi;
    ll lzma;
    node() : lzmi(0), lzma(1e9) {}
};

ll v[sz];
node lz[sz*4];
ll ql, qr, t, x;

void relax(ll pos, ll l, ll r) {
    ll mi = lz[pos].lzmi;
    ll ma = lz[pos].lzma;
    lz[pos].lzmi = 0;
    lz[pos].lzma = 1e9;

    if (l == r) {
        if (v[l] < mi) v[l] = mi;
        else if (v[l] > ma) v[l] = ma;
        return;
    }

    if (mi != 0) {
        lz[pos*2+1].lzmi = max(mi, lz[pos*2+1].lzmi);
        lz[pos*2+2].lzmi = max(mi, lz[pos*2+2].lzmi);
    }

    if (ma != 1e9) {
        lz[pos*2+1].lzma = min(ma, lz[pos*2+1].lzma);
        lz[pos*2+2].lzma = min(ma, lz[pos*2+2].lzma);
    }

    mi = lz[pos*2+1].lzmi;
    ma = lz[pos*2+1].lzma;
    lz[pos*2+1].lzmi = min(mi, ma);
    lz[pos*2+1].lzma = max(mi, ma);

    mi = lz[pos*2+2].lzmi;
    ma = lz[pos*2+2].lzma;
    lz[pos*2+2].lzmi = min(mi, ma);
    lz[pos*2+2].lzma = max(mi, ma);
}

void upd(ll l, ll r, ll pos) {
    relax(pos, l, r);
    if (ql > r || l > qr) return;

    if (ql <= l && r <= qr) {
        if (t == 1) {  // add operation
            lz[pos].lzmi = max(lz[pos].lzmi, x);
            if (lz[pos].lzma < lz[pos].lzmi)
                lz[pos].lzma = lz[pos].lzmi;
        } else {  // min operation
            lz[pos].lzma = min(x, lz[pos].lzma);
            if (lz[pos].lzmi > lz[pos].lzma)
                lz[pos].lzmi = lz[pos].lzma;
        }
        relax(pos, l, r);
        return;
    }

    ll mid = (l + r) / 2;
    upd(l, mid, pos*2+1);
    upd(mid+1, r, pos*2+2);
}

void build(ll l, ll r, ll pos) {
    relax(pos, l, r);
    if (l == r) return;
    ll mid = (l + r) / 2;
    build(l, mid, pos*2+1);
    build(mid+1, r, pos*2+2);
}

void buildWall(ll n, ll k, ll op[], ll left[], ll right[], ll height[], ll finalHeight[]) {
    memset(v, 0, sizeof(v));  // Ensure array is initialized

    for (ll i = 0; i < k; i++) {
        t = op[i];
        ql = left[i];
        qr = right[i];
        x = height[i];
        upd(0, n - 1, 0);
    }

    build(0, n - 1, 0);
    for (ll i = 0; i < n; i++) finalHeight[i] = v[i];
}
/*
int main() {
    AI
    ll n, k;
    cin >> n >> k;
    ll v1[k], v2[k], v3[k], v4[k];
    ll v5[n];

    for (ll i = 0; i < k; i++) {
        cin >> v1[i] >> v2[i] >> v3[i] >> v4[i];
    }

    buildWall(n, k, v1, v2, v3, v4, v5);

    for (ll i = 0; i < n; i++) {
        cout << v5[i] << ' ';
    }
    cout << endl;
    return 0;
}
*/

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