oj.uz

Submission #159576

# Submission time Handle Problem Language Result Execution time Memory
159576 2019-10-23T11:17:46 Z faremy Sails (IOI07_sails) C++14
100 / 100
 262 ms 6776 KB 
#include <iostream>
#include <algorithm>


const int MAXN = 1e5;
const long long INFTY = 1e18;

const int LEAVES = 1 << 17;
const int TSIZE = LEAVES << 1;

int height[MAXN], sails[MAXN];
int order[MAXN];

long long maxAdded[TSIZE];
long long lazy[TSIZE];


void setup()
{
	for (int u = LEAVES; u > 0; u /= 2)
		maxAdded[u] = INFTY;
}

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

	maxAdded[node] += lazy[node];
	lazy[node] = 0;
}

void add(int node, int left, int right, int reqLeft, int reqRight)
{
	push(node);
	if (reqLeft <= left && right <= reqRight)
	{
		lazy[node] = 1;
		push(node);
	}
	else if (reqLeft < right && left < reqRight)
	{
		add(node * 2, left, (left + right) / 2, reqLeft, reqRight);
		add(node * 2 + 1, (left + right) / 2, right, reqLeft, reqRight);
		maxAdded[node] = std::max(maxAdded[node * 2], maxAdded[node * 2 + 1]);
	}
}

long long read(int node, int left, int right, int leaf)
{
	push(node);
	if (right - left == 1)
		return maxAdded[node];
	int middle = (left + right) / 2;

	if (leaf < middle)
		return read(node * 2, left, middle, leaf);
	return read(node * 2 + 1, middle, right, leaf);
}

int leftmost(int node, int left, int right, long long val)
{
	push(node);
	if (maxAdded[node] <= val)
		return -1;	
	if (right - left == 1)
		return right;

	int first = leftmost(node * 2 + 1, (left + right) / 2, right, val);
	if (first == -1)
		return leftmost(node * 2, left, (left + right) / 2, val);
	return first;
}

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

	int masts; std::cin >> masts;
	for (int iMast = 0; iMast < masts; iMast++)
	{
		std::cin >> height[iMast] >> sails[iMast];
		height[iMast]++;
		order[iMast] = iMast;
	}

	std::sort(order, order + masts, [](int a, int b) { return (height[a] < height[b]); });
	setup();

	for (int iMast = 0; iMast < masts; iMast++)
	{
		int mast = order[iMast];
		long long max = read(1, 0, LEAVES, height[mast] - sails[mast]);

		int left = leftmost(1, 0, LEAVES, max);
		int right = std::min(height[mast], leftmost(1, 0, LEAVES, max - 1));

		add(1, 0, LEAVES, right, height[mast]);
		add(1, 0, LEAVES, left, left + sails[mast] - height[mast] + right);
	}

	long long ans = 0;
	for (int iNode = 1; iNode < TSIZE; iNode++)
	{
		push(iNode);
		if (iNode > LEAVES && maxAdded[iNode] > 0)
			ans += maxAdded[iNode] * (maxAdded[iNode] - 1) / 2;
	}

	std::cout << ans << '\n';

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4472 KB Output is correct
2 Correct 7 ms 4472 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4472 KB Output is correct
2 Correct 6 ms 4472 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4472 KB Output is correct
2 Correct 7 ms 4472 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4472 KB Output is correct
2 Correct 8 ms 4472 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4472 KB Output is correct
2 Correct 9 ms 4472 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4572 KB Output is correct
2 Correct 73 ms 5108 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 5180 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 5600 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 6256 KB Output is correct
2 Correct 178 ms 6268 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 6532 KB Output is correct
2 Correct 143 ms 6136 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 6776 KB Output is correct
2 Correct 179 ms 6648 KB Output is correct