oj.uz

Submission #377335

# Submission time Handle Problem Language Result Execution time Memory
377335 2021-03-14T01:39:55 Z applemethod Wall (IOI14_wall) C++14
0 / 100
 1 ms 364 KB 
#include <iostream>
#include <algorithm>

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 (lazy == 0) return;
		if (left_child != NULL) {
			left_child->update(lazy);
		}
		if (right_child != NULL) {
			right_child->update(lazy);
		}
		lazy = 0;
	}

	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++) {
        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 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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