oj.uz

Submission #835492

# Submission time Handle Problem Language Result Execution time Memory
835492 2023-08-23T15:09:41 Z mat_jur Wall (IOI14_wall) C++14
0 / 100
 188 ms 13840 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 = 2147483647; lzmx = -1; mn = mx = 0;}
	};
	vector<Node> tree(2*base);
	auto push_to_sons = [&](int v) {
		int l = tree[v].lzmn, r = tree[v].lzmx;
		if (r == -1) return;
		tree[2*v].mn = max(tree[2*v].mn, l);
		tree[2*v+1].mn = max(tree[2*v+1].mn, l);
		tree[2*v].mx = min(tree[2*v].mx, r);
		tree[2*v+1].mx = min(tree[2*v+1].mx, r);
		tree[2*v].lzmn = max(tree[2*v].lzmn, l);
		tree[2*v+1].lzmn = max(tree[2*v+1].lzmn, l);
		tree[2*v].lzmx = min(tree[2*v].lzmx, r);
		tree[2*v+1].lzmx = min(tree[2*v+1].lzmx, r);
		tree[v].lzmn = 2147483647; 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 = min(tree[v].lzmn, x);	
			tree[v].lzmx = min(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, 2*base-1) {
		assert(tree[i].mn == tree[i].mx);
		finalHeight[i-base] = tree[i].mn;
	}
}

Subtask #1
0 / 8.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 Runtime error 2 ms 564 KB Execution killed with signal 6
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 102 ms 13840 KB Output is correct
3 Runtime error 188 ms 13036 KB Execution killed with signal 6
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 1 ms 340 KB Output is correct
3 Runtime error 2 ms 468 KB Execution killed with signal 6
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 Runtime error 2 ms 468 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -