oj.uz

Submission #1053820

# Submission time Handle Problem Language Result Execution time Memory
1053820 2024-08-11T18:02:14 Z EntityPlantt Wall (IOI14_wall) C++17
24 / 100
 261 ms 13648 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 69 ms 12116 KB Output is correct
3 Correct 91 ms 7832 KB Output is correct
4 Correct 261 ms 13140 KB Output is correct
5 Correct 161 ms 13648 KB Output is correct
6 Correct 176 ms 13620 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 2 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -