oj.uz

Submission #168189

# Submission time Handle Problem Language Result Execution time Memory
168189 2019-12-11T21:56:43 Z johutha Wall (IOI14_wall) C++14
100 / 100
 2375 ms 152056 KB 
#include "wall.h"
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct operation
{
	int minb = -1e9, maxb = 1e9, fixed = -1;

	int apply(int old)
	{
		if (fixed != -1) return fixed;
		return min(maxb, max(minb, old));
	}
};

operation merge(operation o1, operation o2) // o2 after o1
{
	if (o2.fixed != -1)
	{
		return operation{(int)-1e9, (int)1e9, o2.fixed};
	}
	else if (o1.fixed != -1)
	{
		return operation{(int)-1e9, (int)1e9, min(o2.maxb, max(o2.minb, o1.fixed))};
	}

	operation res;
	res.minb = max(o1.minb, o2.minb);
	res.maxb = min(o1.maxb, o2.maxb);

	if (res.maxb <= res.minb)
	{
		res.fixed = (res.minb == o2.minb ? o2.minb : o2.maxb);
		res.minb = -1e9;
		res.maxb = 1e9;
	}

	return res;
}

struct segtree
{
	vector<int> table;
	vector<operation> ops;

	void apply(int pos, operation op)
	{
		ops[pos] = merge(ops[pos], op);
		table[pos] = op.apply(table[pos]);
	}

	void propagate(int pos)
	{
		apply(2*pos + 1, ops[pos]);
		apply(2*pos + 2, ops[pos]);
		ops[pos] = operation();
	}

	void update(int ql, int qr, operation op, int l, int r, int pos)
	{
		if (ql <= l && r <= qr)
		{
			apply(pos, op);
			return;
		}
		if (r < ql || qr < l) return;
		propagate(pos);
		update(ql, qr, op, l, (l + r)/2, 2*pos + 1);
		update(ql, qr, op, (l + r)/2 + 1, r, 2*pos + 2);
	}

	int query(int k, int l, int r, int pos)
	{
		if (l == r) return table[pos];
		propagate(pos);
		if (k <= (l + r)/2) return query(k, l, (l + r)/2, 2*pos + 1);
		else return query(k, (l + r)/2 + 1, r, 2*pos + 2);
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	segtree st;
	st.ops.resize(4*n);
	st.table.resize(4*n);

	for (int i = 0; i < k; i++)
	{
		operation nop;
		if (op[i] == 1) nop.minb = height[i];
		else nop.maxb = height[i];
		st.update(left[i], right[i], nop, 0, n - 1, 0);
	}

	for (int i = 0; i < n; i++)
	{
		finalHeight[i] = st.query(i, 0, n - 1, 0);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 452 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 14 ms 1144 KB Output is correct
5 Correct 13 ms 1148 KB Output is correct
6 Correct 13 ms 1144 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 185 ms 14040 KB Output is correct
3 Correct 359 ms 8816 KB Output is correct
4 Correct 971 ms 24504 KB Output is correct
5 Correct 587 ms 25056 KB Output is correct
6 Correct 561 ms 23488 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 14 ms 1144 KB Output is correct
5 Correct 13 ms 1144 KB Output is correct
6 Correct 13 ms 1144 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 189 ms 13944 KB Output is correct
9 Correct 326 ms 8692 KB Output is correct
10 Correct 974 ms 24620 KB Output is correct
11 Correct 587 ms 24952 KB Output is correct
12 Correct 564 ms 23544 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 184 ms 14072 KB Output is correct
15 Correct 56 ms 2680 KB Output is correct
16 Correct 911 ms 24376 KB Output is correct
17 Correct 563 ms 23900 KB Output is correct
18 Correct 557 ms 23924 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 476 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 14 ms 1144 KB Output is correct
5 Correct 13 ms 1144 KB Output is correct
6 Correct 12 ms 1144 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 183 ms 14004 KB Output is correct
9 Correct 328 ms 8568 KB Output is correct
10 Correct 971 ms 24516 KB Output is correct
11 Correct 588 ms 25080 KB Output is correct
12 Correct 559 ms 23520 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 189 ms 14068 KB Output is correct
15 Correct 56 ms 2552 KB Output is correct
16 Correct 935 ms 24520 KB Output is correct
17 Correct 563 ms 24056 KB Output is correct
18 Correct 556 ms 23796 KB Output is correct
19 Correct 2324 ms 151620 KB Output is correct
20 Correct 2329 ms 151720 KB Output is correct
21 Correct 2327 ms 151900 KB Output is correct
22 Correct 2330 ms 151772 KB Output is correct
23 Correct 2340 ms 152056 KB Output is correct
24 Correct 2375 ms 151704 KB Output is correct
25 Correct 2325 ms 151884 KB Output is correct
26 Correct 2372 ms 151716 KB Output is correct
27 Correct 2345 ms 151728 KB Output is correct
28 Correct 2324 ms 151924 KB Output is correct
29 Correct 2367 ms 151764 KB Output is correct
30 Correct 2309 ms 151760 KB Output is correct