oj.uz

Submission #835547

# Submission time Handle Problem Language Result Execution time Memory
835547 2023-08-23T15:39:09 Z mat_jur Wall (IOI14_wall) C++17
0 / 100
 240 ms 8092 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	int base = 1;
	while (base < n) base *= 2;
	struct Node {
		int mn, mx;
		int lzmn, lzmx;
		Node() {lzmn = -1; lzmx = -1; mn = mx = 0;}
	};
	vector<Node> tree(2*base);
	auto minn = [&](int a, int b) {
		if (a == -1) return b;
		return min(a, b);
	};
	auto push_to_sons = [&](int v) {
		int l = tree[v].lzmn, r = tree[v].lzmx;
		if (r == -1) return;
		tree[2*v].mn = min(max(tree[2*v].mn, l), r);
		tree[2*v+1].mn = min(max(tree[2*v+1].mn, l), r);
		tree[2*v].mx = max(min(tree[2*v].mx, r), l);
		tree[2*v+1].mx = max(min(tree[2*v+1].mx, r), l);
		tree[2*v].lzmn = min(max(tree[2*v].lzmn, l), r);
		tree[2*v+1].lzmn = min(max(tree[2*v+1].lzmn, l), r);
		tree[2*v].lzmx = max(minn(tree[2*v].lzmx, r), l);
		tree[2*v+1].lzmx = max(minn(tree[2*v+1].lzmx, r), l);
		tree[v].lzmn = -1; tree[v].lzmx = -1;
	};
	function<void(int, int, int, int, int, int)> updatemn = [&](int l, int r, int x, int v, int a, int b) {
		if (r < a || b < l) return;
		if (l <= a && b <= r) {
			tree[v].mn = max(tree[v].mn, x);	
			tree[v].mx = max(tree[v].mx, x);	
			tree[v].lzmn = max(tree[v].lzmn, x);	
			tree[v].lzmx = max(tree[v].lzmx, x);	
			return;
		}
		push_to_sons(v);
		int mid = (a+b)/2;
		updatemn(l, r, x, 2*v, a, mid); updatemn(l, r, x, 2*v+1, mid+1, b);
		tree[v].mn = min(tree[2*v].mn, tree[2*v+1].mn);
		tree[v].mx = max(tree[2*v].mx, tree[2*v+1].mx);
	};
	function<void(int, int, int, int, int, int)> updatemx = [&](int l, int r, int x, int v, int a, int b) {
		if (r < a || b < l) return;
		if (l <= a && b <= r) {
			tree[v].mn = min(tree[v].mn, x);	
			tree[v].mx = min(tree[v].mx, x);	
			tree[v].lzmn = minn(tree[v].lzmn, x);	
			tree[v].lzmx = minn(tree[v].lzmx, x);	
			return;
		}
		push_to_sons(v);
		int mid = (a+b)/2;
		updatemx(l, r, x, 2*v, a, mid); updatemx(l, r, x, 2*v+1, mid+1, b);
		tree[v].mn = min(tree[2*v].mn, tree[2*v+1].mn);
		tree[v].mx = max(tree[2*v].mx, tree[2*v+1].mx);
	};
	REP(i, k) {
		if (op[i] == 1) {
			updatemn(left[i], right[i], height[i], 1, 0, base-1);
		}
		else {
			updatemx(left[i], right[i], height[i], 1, 0, base-1);
		}
	}
	FOR(i, 1, base-1) {
		push_to_sons(i);
	}
	FOR(i, base, base+n-1) {
		assert(tree[i].mn == tree[i].mx);
//		cerr << tree[i].mn << ' ' << tree[i].mx << '\n';
		finalHeight[i-base] = tree[i].mn;
	}
}
/*
#ifdef LOCAL
int main () {
	int n, k;
	cin >> n >> k;
	REP(i, k) {
		int 
	}
}
#endif
*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 2 ms 340 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 212 KB Output is correct
2 Correct 119 ms 8092 KB Output is correct
3 Incorrect 240 ms 4636 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 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 3 ms 340 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 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 3 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -