oj.uz

Submission #856867

# Submission time Handle Problem Language Result Execution time Memory
856867 2023-10-04T18:04:49 Z promitheas Wall (IOI14_wall) C++14
0 / 100
 117 ms 13968 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

template<typename T>
T max(T a, T b) {
    return a < b ? b : a;
}
template<typename T>
T min(T a, T b) {
    return a > b ? b : a;
}

template<typename T>
void minset(T& a, T b) {
    a = min(a, b);
}

template<typename T>
void maxset(T& a, T b) {
    a = max(a, b);
}

class Node {
public:
    Node* left;
    Node* right;
    bool hasLazy = false;
    void Propagate() {
        if (!left)left = new Node();
        if (!right)right = new Node();
        /*
        left->lo = max(left->lo, lo);
        left->hi = max(left->hi, hi);
        right->lo = max(right->lo, lo);
        right->hi = max(right->hi, hi);
        */
        minset(left->lo, this->hi);
        maxset(left->lo, this->lo);
        minset(right->lo, this->hi);
        maxset(right->lo, this->lo);

        minset(left->hi, this->hi);
        maxset(left->hi, this->lo);
        minset(right->hi, this->hi);
        maxset(right->hi, this->lo);
    }
    Node* L() {
        if (!left)left = new Node();
        if (hasLazy) {
            Propagate();
            hasLazy = false;
        }
        return left;
    }
    Node* R() {
        if (!right)right = new Node();
        if (hasLazy) {
            Propagate();
            hasLazy = false;
        }
        return right;
    }
    int lo;
    int hi;
	void BuildUp(int l, int r, int tl, int tr, int h) {
		if (l == tl && r == tr) {
			lo = max(lo, h); //bring lo to at least h
			hi = max(hi, lo); // hi must be at least lo
			hasLazy = true;
			return;
		}
		int mid = (l + r) >> 1;
		if (tr <= mid) {
			return L()->BuildUp(l, mid, tl, tr, h);
		}
		if (tl > mid) {
			return R()->BuildUp(mid + 1, r, tl, tr, h);
		}
		L()->BuildUp(l, mid, tl, mid, h);
		R()->BuildUp(mid + 1, r, mid + 1, tr, h);
	}

	void BreakDown(int l, int r, int tl, int tr, int h) {
		if (l == tl && r == tr) {
			hi = min(hi, h);
			lo = min(lo, h);
			hasLazy = true;
			return;
		}
		int mid = (l + r) >> 1;
		if (tr <= mid) {
			return L()->BreakDown(l, mid, tl, tr, h);
		}
		if (tl > mid) {
			return R()->BreakDown(mid + 1, r, tl, tr, h);
		}
		L()->BreakDown(l, mid, tl, mid, h);
		R()->BreakDown(mid + 1, r, mid + 1, tr, h);
	}

	int GetVal(int l, int r, int t) {
		if (l == r)
			return lo;
		int mid = (l + r) >> 1;
		if (t <= mid)
			return L()->GetVal(l, mid, t);
		return R()->GetVal(mid + 1, r, t);
	}
};

Node* node;

int N;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	node = new Node();
	for (int i = 0; i < k; i++) {
		if (op[i] == 1)
			node->BuildUp(0, n - 1, left[i], right[i], height[i]);
		else
			node->BreakDown(0, n - 1, left[i], right[i], height[i]);
	}
	for (int i = 0; i < n; i++) {
		finalHeight[i] = node->GetVal(0, n - 1, i);
	}
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 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 348 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Incorrect 1 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -