Submission #1271080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271080		baotoan655	Wall (IOI14_wall)	C++20	100 / 100	493 ms	152036 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;

const int inf = 1e9 + 7;
const int N = 2e6 + 5;
struct node {
    int mn, mx;
    node(int _mn = 0, int _mx = inf) {
        mn = _mn;
        mx = _mx;
    }
    node operator + (const node& o) const {
        node res;
        res.mn = max(mn, o.mn);
        res.mx = max(res.mn, mx);
        res.mx = min(res.mx, o.mx);
        res.mn = min(res.mx, res.mn);
        return res;
    }
} it[N << 2], lazy[N << 2];

void upd(int k, node val){
    it[k] = it[k] + val;
    lazy[k] = lazy[k] + val;
}
void shift(int k) {
    upd(k << 1, lazy[k]);
    upd(k << 1 | 1, lazy[k]);
    lazy[k] = node();
}
void update(int k, int l, int r, int u, int v, node val) {
    if(l > v || r < u) return;
    if(u <= l && r <= v) {
        upd(k, val);
        return;
    }
    shift(k);
    int mid = l + r >> 1;
    update(k << 1, l, mid, u, v, val);
    update(k << 1 | 1, mid + 1, r, u, v, val);
}
void get(int k, int l, int r, int *res) {
    if(l == r) {
        res[l - 1] = it[k].mn;
        return;
    }
    shift(k);
    int mid = l + r >> 1;
    get(k << 1, l, mid, res);
    get(k << 1 | 1, mid + 1, r, res);
}

void buildWall(int n, int k, int op[], int L[], int R[], int H[], int res[]) {
    for(int i = 0; i < k; ++i) {
        if(op[i] == 1) {
            update(1, 1, n, L[i] + 1, R[i] + 1, node(H[i], inf));
        } else {
            update(1, 1, n, L[i] + 1, R[i] + 1, node(0, H[i]));
        }
    }
    get(1, 1, n, res);
}

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