oj.uz

Submission #377345

# Submission time Handle Problem Language Result Execution time Memory
377345 2021-03-14T04:00:29 Z applemethod Wall (IOI14_wall) C++14
0 / 100
 212 ms 14172 KB 
#include <iostream>
#include <algorithm>

#include "wall.h"

using namespace std;

using ll = long long;

const int maxn = 2000010;

struct segtree_node {
	segtree_node* left_child, * right_child;
	int left_bound, right_bound;
	ll lazy;

	void update(ll val) {
		if (val < 0) {
			lazy = max(lazy, -val);
		} else {
			lazy = min(lazy, val);
		}
	}
	void merge() {

	}
	void prop() {
		if (left_child != NULL) {
			left_child->update(lazy);
		}
		if (right_child != NULL) {
			right_child->update(lazy);
		}
	}

	void update(int left, int right, ll val) {
		prop();
		if (left_bound >= left && right_bound <= right) {
			update(val);
			return;
		}
		int mid = left_bound + (right_bound - left_bound) / 2;
		if (left <= mid) {
			if (left_child == NULL) {
				left_child = new segtree_node(left_bound, mid);
			}
			left_child->update(left, right, val);
		}
		if (right > mid) {
			if (right_child == NULL) {
				right_child = new segtree_node(mid + 1, right_bound);
			}
			right_child->update(left, right, val);
		}
		merge();
	}
	ll query(int left, int right) {
		prop();
		if (left_bound >= left && right_bound <= right) {
			return lazy;
		}
		int mid = left_bound + (right_bound - left_bound) / 2;
		ll res = 0;
		if (left <= mid) {
			if (left_child == NULL) {
				left_child = new segtree_node(left_bound, mid);
			}
			res += left_child->query(left, right);
		}
		if (right > mid) {
			if (right_child == NULL) {
				right_child = new segtree_node(mid + 1, right_bound);
			}
			res += right_child->query(left, right);
		}
		return res;
	}

	segtree_node() {
		left_child = right_child = NULL;
		left_bound = right_bound = -1;
		lazy = 0;
	}
	segtree_node(int left, int right) {
		left_child = right_child = NULL;
		left_bound = left; right_bound = right;
		lazy = 0;
	}
};

segtree_node* segtree;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	segtree = new segtree_node(0, n - 1);
	for (int i = 0; i < k; i++) {
		// cout << (op[i] * 2 - 3) * height[i] << endl;
		segtree->update(left[i], right[i], (op[i] * 2 - 3) * height[i]);
	}
	for (int i = 0; i < n; i++) {
		finalHeight[i] = segtree->query(i, i);
	}
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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