oj.uz

Submission #203465

# Submission time Handle Problem Language Result Execution time Memory
203465 2020-02-20T20:07:55 Z faremy Pyramid Base (IOI08_pyramid_base) C++14
100 / 100
 1844 ms 72116 KB 
#include <iostream>
#include <algorithm>
#include <vector>


class Interval
{
	int left, right;

public:
	Interval(int l, int r) : left(l), right(r) {}

	bool IsIncludedIn(const Interval &other) const
	{
		return (other.left <= left && right <= other.right);
	}

	bool IsDisjointFrom(const Interval &other) const
	{
		return (other.right <= left || right <= other.left);
	}

	Interval Left() const
	{
		return Interval(left, (left + right) / 2);
	}

	Interval Right() const
	{
		return Interval((left + right) / 2, right);
	}

	int Size() const
	{
		return (right - left);
	}
};

struct Side
{
	Side(int p, int l, int r, long long v) : position(p), covers(l, r), value(v) {}
	int position;
	Interval covers;
	long long value;

	bool operator <(const Side &other) const
	{
		return (position < other.position);
	}
};

const int MAXP = 4e5;
const int MAXN = 1e6 + 1;
const long long INFTY = 1e18;

const int LEAVES = 1 << 20;
const int TSIZE = LEAVES << 1;
const Interval ROOTCOVER = { 0, LEAVES };

int left[MAXP], bottom[MAXP];
int right[MAXP], top[MAXP];
long long cost[MAXP];

long long minCovering[TSIZE];
long long covering[TSIZE];
std::vector<Side> obstacleLimits;

int on[TSIZE];
int emptyLeft[TSIZE], emptyRight[TSIZE];
int maxEmpty[TSIZE];
std::vector<Side> plus, minus;


void push(int node)
{
	if (node < LEAVES)
	{
		covering[node * 2] += covering[node];
		covering[node * 2 + 1] += covering[node];
	}

	minCovering[node] += covering[node];
	covering[node] = 0;
}

void update(int node, Interval covered, Interval requested, long long value)
{
	push(node);
	if (covered.IsIncludedIn(requested))
	{
		covering[node] = value;
		push(node);
	}
	else if (!covered.IsDisjointFrom(requested))
	{
		update(node * 2, covered.Left(), requested, value);
		update(node * 2 + 1, covered.Right(), requested, value);
		minCovering[node] = std::min(minCovering[node * 2], minCovering[node * 2 + 1]);
	}
}

long long getmin(int node, Interval covered, Interval requested)
{
	push(node);
	if (covered.IsIncludedIn(requested))
		return minCovering[node];
	if (covered.IsDisjointFrom(requested))
		return INFTY;
	return std::min(getmin(node * 2, covered.Left(), requested), getmin(node * 2 + 1, covered.Right(), requested));
}

void buildlimits(int squareSize, int obstacles, int width, int height)
{
	obstacleLimits.clear();
	std::fill_n(minCovering, TSIZE, 0);
	std::fill_n(covering, TSIZE, 0);

	for (int iObst = 0; iObst < obstacles; iObst++)
	{
		int trueLeft = std::max(0, left[iObst] - squareSize);
		int trueBottom = std::max(0, bottom[iObst] - squareSize);
		int trueTop = std::min(height - squareSize + 1, top[iObst]);

		obstacleLimits.emplace_back(trueLeft, trueBottom, trueTop, cost[iObst]);
		if (right[iObst] < width - squareSize + 1)
			obstacleLimits.emplace_back(right[iObst], trueBottom, top[iObst], -cost[iObst]);
	}

	std::sort(obstacleLimits.begin(), obstacleLimits.end());
}

bool isvalidsize(int squareSize, int obstacles, int width, int height, long long budget)
{
	buildlimits(squareSize, obstacles, width, height);
	for (int iLim = 0; iLim < (int)obstacleLimits.size();)
	{
		for (int jLim = iLim; iLim < (int)obstacleLimits.size() && obstacleLimits[iLim].position == obstacleLimits[jLim].position; iLim++)
			update(1, ROOTCOVER, obstacleLimits[iLim].covers, obstacleLimits[iLim].value);
		if (getmin(1, ROOTCOVER, Interval(0, height - squareSize + 1)) <= budget)
			return true;
	}

	return false;
}

int maxsquare(int smallest, int largest, int obstacles, int width, int height, long long budget)
{
	if (smallest == largest)
		return 0;
	int squareSize = (smallest + largest) / 2;

	if (isvalidsize(squareSize, obstacles, width, height, budget))
		return std::max(squareSize, maxsquare(squareSize + 1, largest, obstacles, width, height, budget));
	return maxsquare(smallest, squareSize, obstacles, width, height, budget);
}

void merge(int node, int size)
{
	int l = (on[node * 2] <= 0);
	int r = (on[node * 2 + 1] <= 0);

	maxEmpty[node] = std::max(std::max(l * maxEmpty[node * 2], r * maxEmpty[node * 2 + 1]), l * emptyRight[node * 2] + r * emptyLeft[node * 2 + 1]);
	emptyLeft[node] = l * emptyLeft[node * 2] + (l * emptyLeft[node * 2] == size / 2) * r * emptyLeft[node * 2 + 1];
	emptyRight[node] = r * emptyRight[node * 2 + 1] + (r * emptyRight[node * 2 + 1] == size / 2) * l * emptyRight[node * 2];
}

void setup(int width)
{
	for (int iLeaf = LEAVES; iLeaf < LEAVES + width; iLeaf++)
	{
		emptyLeft[iLeaf] = 1;
		emptyRight[iLeaf] = 1;
		maxEmpty[iLeaf] = 1;
	}

	int node = LEAVES - 1;
	for (int iSize = LEAVES / 2; iSize > 0; iSize /= 2)
		for (int iPos = 0; iPos < iSize; iPos++)
		{
			merge(node, LEAVES / iSize);
			node--;
		}
}

void add(int node, Interval covered, Interval requested, int val)
{
	if (covered.IsIncludedIn(requested))
		on[node] += val;
	else if (!covered.IsDisjointFrom(requested))
	{
		add(node * 2, covered.Left(), requested, val);
		add(node * 2 + 1, covered.Right(), requested, val);
		merge(node, covered.Size());
	}
}

int B0(int obstacles, int width, int height)
{
	for (int iObst = 0; iObst < obstacles; iObst++)
	{
		plus.emplace_back(bottom[iObst], left[iObst] - 1, right[iObst], 1);
		minus.emplace_back(top[iObst], left[iObst] - 1, right[iObst], -1);
	}

	std::sort(plus.begin(), plus.end());
	std::sort(minus.begin(), minus.end());
	setup(width);

	int upper = 0, p = 0, m = 0, maxSize = 0;
	for (int lower = 0; lower <= height; lower++)
	{
		while (m < (int)minus.size() && minus[m].position == lower)
		{
			add(1, ROOTCOVER, minus[m].covers, -1);
			m++;
		}

		while (maxEmpty[1] >= upper - lower && upper <= height)
		{
			maxSize = std::max(maxSize, upper - lower);
			upper++;

			while (p < (int)plus.size() && plus[p].position == upper)
			{
				add(1, ROOTCOVER, plus[p].covers, 1);
				p++;
			}
		}
	}

	return maxSize;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(nullptr);
	std::cin.tie(nullptr);

	int width, height;
	std::cin >> width >> height;

	long long budget; std::cin >> budget;
	int obstacles; std::cin >> obstacles;

	for (int iObst = 0; iObst < obstacles; iObst++)
		std::cin >> left[iObst] >> bottom[iObst] >> right[iObst] >> top[iObst] >> cost[iObst];
	if (budget == 0)
		std::cout << B0(obstacles, width, height) << '\n';
	else
		std::cout << maxsquare(1, std::min(width, height) + 1, obstacles, width, height, budget) << '\n';

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12796 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12792 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12792 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 13048 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 14876 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 29304 KB Output is correct
2 Correct 39 ms 30072 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 27128 KB Output is correct
2 Correct 40 ms 29432 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 33784 KB Output is correct
2 Correct 194 ms 33976 KB Output is correct
3 Correct 185 ms 33976 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 34932 KB Output is correct
2 Correct 682 ms 34988 KB Output is correct
3 Correct 583 ms 34992 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 35188 KB Output is correct
2 Correct 113 ms 35824 KB Output is correct
3 Correct 235 ms 35060 KB Output is correct
4 Correct 777 ms 35952 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 904 ms 36332 KB Output is correct
2 Correct 1495 ms 36212 KB Output is correct
3 Correct 396 ms 35444 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 36460 KB Output is correct
2 Correct 1766 ms 36588 KB Output is correct
3 Correct 1826 ms 36464 KB Output is correct
4 Correct 1779 ms 36464 KB Output is correct
5 Correct 1844 ms 36464 KB Output is correct
6 Correct 388 ms 36592 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 52484 KB Output is correct
2 Correct 483 ms 51840 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 794 ms 61912 KB Output is correct
2 Correct 893 ms 62068 KB Output is correct
3 Correct 460 ms 43864 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1030 ms 68428 KB Output is correct
2 Correct 1402 ms 72028 KB Output is correct
3 Correct 1382 ms 71940 KB Output is correct
4 Correct 1251 ms 71840 KB Output is correct
5 Correct 898 ms 72116 KB Output is correct