oj.uz

Submission #596472

# Submission time Handle Problem Language Result Execution time Memory
596472 2022-07-14T19:08:22 Z Elias Wall (IOI14_wall) C++17
100 / 100
 745 ms 130660 KB 
#include <bits/stdc++.h>

using namespace std;

#ifndef _DEBUG
#include "wall.h"
#endif

template <class T>
istream &operator>>(istream &in, vector<T> &a)
{
	for (auto &x : a)
		in >> x;
	return in;
}

int minusMin(int a, int b)
{
	if (a == -1)
		return b;
	if (b == -1)
		return a;
	return min(a, b);
}

int minusMax(int a, int b)
{
	if (a == -1)
		return b;
	if (b == -1)
		return a;
	return max(a, b);
}

struct Node
{
	int low = -1;
	int high = -1;
	bool first = 0;

	void Apply(Node update)
	{

		if (this->low == -1 && this->high == -1)
		{
			*this = update;
			return;
		}
		if (update.low == -1 && update.high == -1)
			return;

		low = minusMax(low, update.low);
		high = minusMin(high, update.high);

		if (low > high && high != -1)
		{
			low = high = ((low == update.low) ? update.low : update.high);
		}

		bool a = low == update.low && low != -1;
		bool b = high == update.high && high != -1;

		if (a && b)
			first = update.low;
		else if (a)
			first = 0;
		else if (b)
			first = 1;
	}
};

Node emp = {-1, -1, 0};

vector<Node> b;

void updateRange(int l, int r, int i, int ul, int ur, Node up)
{
	if (l >= ur || r <= ul)
		return;
	if (l >= ul && r <= ur)
	{
		b[i].Apply(up);
		return;
	}

	b[i * 2 + 1].Apply(b[i]);
	b[i * 2 + 2].Apply(b[i]);

	b[i] = emp;

	int m = (l + r) / 2;
	updateRange(l, m, i * 2 + 1, ul, ur, up);
	updateRange(m, r, i * 2 + 2, ul, ur, up);
}

void extractValues(int l, int r, int i, int a[])
{
	if (l + 1 == r)
	{
		a[l] = max(b[i].low, 0);
		return;
	}

	b[i * 2 + 1].Apply(b[i]);
	b[i * 2 + 2].Apply(b[i]);

	b[i] = emp;

	int m = (l + r) / 2;
	extractValues(l, m, i * 2 + 1, a);
	extractValues(m, r, i * 2 + 2, a);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{

	b = vector<Node>(n * 4, emp);

	for (int i = 0; i < k; i++)
		updateRange(0, n, 0, left[i], right[i] + 1, ((op[i] == 1) ? Node{height[i], -1, 0} : Node{-1, height[i], 1}));

	extractValues(0, n, 0, finalHeight);
}

#ifdef _DEBUG

signed main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	int n, k;
	cin >> n >> k;

	vector<int> op, left, right, height;
	op = left = right = height = vector<int>(k);
	cin >> op >> left >> right >> height;

	vector<int> finalHeight(n);

	buildWall(n, k, op, left, right, height, finalHeight);

	for (int &x : finalHeight)
		cout << x << " ";
	cout << "\n";
}

#endif

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 3 ms 360 KB Output is correct
4 Correct 8 ms 980 KB Output is correct
5 Correct 5 ms 1012 KB Output is correct
6 Correct 5 ms 980 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 218 ms 13912 KB Output is correct
3 Correct 306 ms 8264 KB Output is correct
4 Correct 689 ms 22940 KB Output is correct
5 Correct 294 ms 24028 KB Output is correct
6 Correct 299 ms 22480 KB Output is correct

Subtask #3
29.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 Correct 2 ms 340 KB Output is correct
4 Correct 8 ms 948 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 6 ms 1008 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 177 ms 13904 KB Output is correct
9 Correct 229 ms 8240 KB Output is correct
10 Correct 718 ms 22960 KB Output is correct
11 Correct 330 ms 24004 KB Output is correct
12 Correct 317 ms 22432 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 152 ms 14012 KB Output is correct
15 Correct 42 ms 2288 KB Output is correct
16 Correct 745 ms 23200 KB Output is correct
17 Correct 306 ms 22624 KB Output is correct
18 Correct 351 ms 22624 KB Output is correct

Subtask #4
39.0 / 39.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 Correct 2 ms 312 KB Output is correct
4 Correct 8 ms 980 KB Output is correct
5 Correct 5 ms 984 KB Output is correct
6 Correct 8 ms 980 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 145 ms 13888 KB Output is correct
9 Correct 244 ms 8256 KB Output is correct
10 Correct 631 ms 22940 KB Output is correct
11 Correct 271 ms 24012 KB Output is correct
12 Correct 291 ms 22380 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 134 ms 13928 KB Output is correct
15 Correct 43 ms 2192 KB Output is correct
16 Correct 668 ms 23204 KB Output is correct
17 Correct 290 ms 22588 KB Output is correct
18 Correct 273 ms 22628 KB Output is correct
19 Correct 693 ms 130548 KB Output is correct
20 Correct 671 ms 128032 KB Output is correct
21 Correct 677 ms 130660 KB Output is correct
22 Correct 693 ms 128092 KB Output is correct
23 Correct 690 ms 128116 KB Output is correct
24 Correct 675 ms 128052 KB Output is correct
25 Correct 662 ms 128052 KB Output is correct
26 Correct 665 ms 130548 KB Output is correct
27 Correct 674 ms 130604 KB Output is correct
28 Correct 672 ms 128076 KB Output is correct
29 Correct 680 ms 128116 KB Output is correct
30 Correct 663 ms 128084 KB Output is correct