#include "wall.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for (int i = 0; i < (n); i++) #define st first #define nd second #define pb push_back #define pii pair<int, int> #define all(a) a.begin(), a.end() const int MAXN = 1 << 21; const int INF = 1e9; int n, q; int seg[2 * MAXN]; int kop[2 * MAXN][3]; void kopnij(int v) { int a = 2 * v; int b = 2 * v + 1; // cout << "v = " << v << " seg = " << seg[v] << '\n'; // cout << "KOP = "; // rep(c, 3) cout << kop[v][c] << " "; // cout << '\n'; if (kop[v][2] != -1) { seg[a] = kop[v][2]; seg[b] = kop[v][2]; kop[a][2] = kop[v][2]; kop[b][2] = kop[v][2]; kop[a][0] = INF; kop[b][0] = INF; kop[a][1] = 0; kop[b][1] = 0; kop[v][2] = -1; } seg[a] = min(seg[a], kop[v][0]); seg[a] = max(seg[a], kop[v][1]); seg[b] = min(seg[b], kop[v][0]); seg[b] = max(seg[b], kop[v][1]); if (kop[v][0] < kop[a][1]) { kop[a][2] = kop[v][0]; kop[a][1] = 0; } if (kop[a][0] < kop[v][1]) { kop[a][2] = kop[v][1]; kop[a][0] = INF; } if (kop[v][0] < kop[b][1]) { // cout << "PLSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS" << '\n'; kop[b][2] = kop[v][0]; kop[b][1] = 0; } if (kop[b][0] < kop[v][1]) { kop[b][2] = kop[v][1]; kop[b][0] = INF; } kop[a][0] = min(kop[a][0], kop[v][0]); kop[a][1] = max(kop[a][1], kop[v][1]); kop[b][0] = min(kop[b][0], kop[v][0]); kop[b][1] = max(kop[b][1], kop[v][1]); kop[v][0] = INF; kop[v][1] = 0; } void upd(int v, int l, int r, int p, int k, int c, int h) { if (p <= l && r <= k) { // cout << "v = " << v << " c = " << c << " h = " << h << '\n'; if (c == 1) { seg[v] = min(seg[v], h); kop[v][0] = min(kop[v][0], h); if (kop[v][1] > kop[v][0]) { kop[v][2] = h; kop[v][1] = 0; } } else { seg[v] = max(seg[v], h); kop[v][1] = max(kop[v][1], h); if (kop[v][0] < kop[v][1]) { kop[v][2] = h; kop[v][0] = INF; } } } else if (p > r || k < l) { } else { kopnij(v); int sr = (l + r)/2; upd(2 * v, l, sr, p, k, c, h); upd(2 * v + 1, sr + 1, r, p, k, c, h); } } void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ rep(i, 2 * MAXN) { kop[i][0] = INF; } n = N; q = k; rep(i, q) { op[i] = 3 - op[i]; upd(1, 0, MAXN - 1, left[i], right[i], op[i], height[i]); } for (int v = 1; v < MAXN; v++) { kopnij(v); } rep(i, n) { finalHeight[i] = seg[i + MAXN]; } return; }