oj.uz

Submission #163550

# Submission time Handle Problem Language Result Execution time Memory
163550 2019-11-13T19:24:11 Z faremy Pyramid Base (IOI08_pyramid_base) C++14
46 / 100
 5000 ms 102876 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);
	}
};

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

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[MAXN];


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)
{
	for (int iPos = 0; iPos <= width; iPos++)
		obstacleLimits[iPos].clear();
	std::fill_n(minCovering, TSIZE, 0);
	std::fill_n(covering, TSIZE, 0);

	for (int iObst = 0; iObst < obstacles; iObst++)
	{
		obstacleLimits[std::max(0, left[iObst] - squareSize)].emplace_back(std::max(0, bottom[iObst] - squareSize), top[iObst], cost[iObst]);
		obstacleLimits[right[iObst]].emplace_back(std::max(0, bottom[iObst] - squareSize), top[iObst], -cost[iObst]);
	}
}

bool isvalidsize(int squareSize, int obstacles, int width, int height, long long budget)
{
	buildlimits(squareSize, obstacles, width);
	for (int iPos = 0; iPos < width - squareSize + 1; iPos++)
	{
		for (Side &seg : obstacleLimits[iPos])
			update(1, ROOTCOVER, seg.covers, seg.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);
}

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];
	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 83 ms 56696 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 56696 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 56740 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 56824 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 57128 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 969 ms 56992 KB Output is correct
2 Execution timed out 5076 ms 57260 KB Time limit exceeded

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5016 ms 57432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 57180 KB Output is correct
2 Correct 248 ms 57532 KB Output is correct
3 Correct 270 ms 57592 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 763 ms 59708 KB Output is correct
2 Correct 1176 ms 60788 KB Output is correct
3 Correct 1106 ms 61044 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1991 ms 62196 KB Output is correct
2 Correct 624 ms 61816 KB Output is correct
3 Correct 258 ms 58740 KB Output is correct
4 Correct 3993 ms 66676 KB Output is correct

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3503 ms 65012 KB Output is correct
2 Execution timed out 5054 ms 65776 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2715 ms 63220 KB Output is correct
2 Execution timed out 5095 ms 67604 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5114 ms 88332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5086 ms 95500 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5037 ms 102876 KB Time limit exceeded
2 Halted 0 ms 0 KB -