Submission #1053820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053820		EntityPlantt	벽 (IOI14_wall)	C++17	24 / 100	261 ms	13648 KiB

wall

#include "wall.h"
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const int S = (1 << 22) + 5;
int lazyl[S], lazyh[S], s;
// lazylastoper[i] = is the last operation on i removal
bool lazylastoper[S];

void sgtprop(int p, int c) {
	lazyh[c] = max(lazyh[c], lazyh[p]);
	lazyl[c] = min(lazyl[c], lazyl[p]);
	if (lazyl[c] < lazyh[c]) {
		if (lazylastoper[p]) lazyl[c] = lazyh[c];
		else lazyh[c] = lazyl[c];
	}
	lazylastoper[c] = lazylastoper[p];
}
void sgtprop(int nd) {
	if (nd >= s) return;
	sgtprop(nd, 2 * nd + 1);
	sgtprop(nd, 2 * nd + 2);
	lazyh[nd] = 0;
	lazyl[nd] = 1e7;
}
void sgtupd(int l, int r, int op, int height, int node, int cl, int cr) {
	if (cr < l || r < cl) return;
	if (l <= cl && cr <= r) {
		lazylastoper[node] = op == 2;
		if (op == 1) {
			lazyh[node] = max(lazyh[node], height);
			lazyl[node] = max(lazyl[node], height);
		}
		else {
			lazyh[node] = min(lazyh[node], height);
			lazyl[node] = min(lazyl[node], height);
		}
		return;
	}
	sgtprop(node);
	int mid = cl + cr >> 1;
	sgtupd(l, r, op, height, 2 * node + 1, cl, mid);
	sgtupd(l, r, op, height, 2 * node + 2, mid + 1, cr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	s = 1 << int(ceil(log2(n))); s--;
	for (int i = 0; i < 2 * s + 2; i++) lazyl[i] = 1e7;
	for (int i = 0; i < k; i++) sgtupd(left[i], right[i], op[i], height[i], 0, 0, s);
	for (int i = 0; i < s; i++) sgtprop(i);
	for (int i = 0; i < n; i++) finalHeight[i] = lazyh[s + i];
}

Compilation message (stderr)

wall.cpp: In function 'void sgtupd(int, int, int, int, int, int, int)':
wall.cpp:43:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |  int mid = cl + cr >> 1;
      |            ~~~^~~~

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