oj.uz

Submission #160167

# Submission time Handle Problem Language Result Execution time Memory
160167 2019-10-26T08:36:45 Z tuna Wall (IOI14_wall) C++14
24 / 100
 1030 ms 50808 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define lc (id << 1)
#define mid ((l + r) >> 1)
#define rc ((id << 1) | 1)
using namespace std;

const int N = 1 << 21, inf = 1 << 17;

int tree[N], d[N << 1], u[N << 1];

void merge(int id, int c) {
	if (d[id] <= d[c]) {
		if (u[id] <= d[c]) {
			d[c] = u[c] = u[id];
		}
		if (d[c] < u[id] && u[id] <= u[c]) {
			u[c] = u[id];
		}
	}
	if (d[c] < d[id] && d[id] <= u[c]) {
		if (u[id] <= u[c]) {
			d[c] = d[id];
			u[c] = u[id];
		} else {
			d[c] = d[id];
		}
	}
	if (u[c] < d[id]) {
		d[c] = d[id];
		u[c] = u[id];
	}
}

void push(int id) {
	if (id >= N) {
		tree[id - N] = max(tree[id - N], d[id]);
		tree[id - N] = min(tree[id - N], u[id]);
	} else {
		merge(id, lc);
		merge(id, rc);
	}
	d[id] = 0;
	u[id] = inf;
}

void update(int id, int l, int r, int L, int R, int vd, int vu) {
	push(id);
	if (l > R || r < L) {
		return;
	}
	if (L <= l && r <= R) {
		d[id] = vd;
		u[id] = vu;
		return;
	}
	update(lc, l, mid, L, R, vd, vu);
	update(rc, mid + 1, r, L, R, vd, vu);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	fill(u, u + N, inf);
	for (int i = 0; i < k; i++) {
		if (op[i] == 1) {
			update(1, 1, N, left[i] + 1, right[i] + 1, height[i], inf);
		} else {
			update(1, 1, N, left[i] + 1, right[i] + 1, 0, height[i]);
		}
	}
	for (int id = 1; id < N << 1; id++) {
		push(id);
	}
	for (int i = 0; i < n; i++) {
		finalHeight[i] = tree[i];
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 41336 KB Output is correct
2 Correct 81 ms 41372 KB Output is correct
3 Incorrect 78 ms 41464 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 79 ms 41416 KB Output is correct
2 Correct 592 ms 49280 KB Output is correct
3 Correct 435 ms 44792 KB Output is correct
4 Correct 1030 ms 50296 KB Output is correct
5 Correct 584 ms 50808 KB Output is correct
6 Correct 580 ms 50728 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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