Submission #159576

#	Time	Username	Problem	Language	Result	Execution time	Memory
159576		faremy	Sails (IOI07_sails)	C++14	100 / 100	262 ms	6776 KiB

sails

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10