Submission #1147704

#TimeUsernameProblemLanguageResultExecution timeMemory
1147704brianhdzmdo벽 (IOI14_wall)C++20
24 / 100
349 ms14004 KiB
#include <iostream> #include <algorithm> using namespace std; const int N = 2000005; const int INF = 1000000000; int ST[4 * N], lazyMax[4 * N], lazyMin[4 * N]; void init(int n) { for (int i = 1; i < 4 * n; i++) { ST[i] = 0; lazyMax[i] = -1; lazyMin[i] = INF; } } void propagate(int node, int l, int r) { if (lazyMax[node] != -1) { ST[node] = max(ST[node], lazyMax[node]); if (l != r) { int left = 2 * node, right = 2 * node + 1; lazyMax[left] = max(lazyMax[left], lazyMax[node]); lazyMax[right] = max(lazyMax[right], lazyMax[node]); } lazyMax[node] = -1; } if (lazyMin[node] != INF) { ST[node] = min(ST[node], lazyMin[node]); if (l != r) { int left = 2 * node, right = 2 * node + 1; lazyMin[left] = min(lazyMin[left], lazyMin[node]); lazyMin[right] = min(lazyMin[right], lazyMin[node]); } lazyMin[node] = INF; } } void updateMax(int node, int l, int r, int a, int b, int h) { propagate(node, l, r); if (l > b || r < a) { return; } if (a <= l && r <= b) { lazyMax[node] = h; propagate(node, l, r); return; } int mid = (l + r) / 2, left = 2 * node, right = 2 * node + 1; updateMax(left, l, mid, a, b, h); updateMax(right, mid + 1, r, a, b, h); ST[node] = max(ST[left], ST[right]); } void updateMin(int node, int l, int r, int a, int b, int h) { propagate(node, l, r); if (l > b || r < a) { return; } if (a <= l && r <= b) { lazyMin[node] = h; propagate(node, l, r); return; } int mid = (l + r) / 2, left = 2 * node, right = 2 * node + 1; updateMin(left, l, mid, a, b, h); updateMin(right, mid + 1, r, a, b, h); ST[node] = min(ST[left], ST[right]); } void buildFinalHeights(int node, int l, int r, int finalHeight[]) { propagate(node, l, r); if (l == r) { finalHeight[l] = ST[node]; return; } int mid = (l + r) / 2, left = 2 * node, right = 2 * node + 1; buildFinalHeights(left, l, mid, finalHeight); buildFinalHeights(right, mid + 1, r, finalHeight); } void buildWall(int n, int k, int op[], int leftArr[], int rightArr[], int height[], int finalHeight[]) { init(n); for (int i = 0; i < k; i++) { int a = leftArr[i], b = rightArr[i], h = height[i]; if (op[i] == 1) { updateMax(1, 0, n - 1, a, b, h); } else { updateMin(1, 0, n - 1, a, b, h); } } buildFinalHeights(1, 0, n - 1, finalHeight); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...