Submission #473755

#	Time	Username	Problem	Language	Result	Execution time	Memory
473755		flashmt	Sails (IOI07_sails)	C++17	100 / 100	177 ms	4256 KiB

sails

#include <bits/stdc++.h>
using namespace std;
const int N = 100100;

int n, H, f[N * 4], mn[N * 4];
vector<pair<int, int>> a;

int get(int nd, int l, int r, int x)
{
	if (l == r) return f[nd];
	int m = (l + r) / 2;
	if (x <= m) return f[nd] + get(nd * 2, l, m, x);
	return f[nd] + get(nd * 2 + 1, m + 1, r, x);
}

int find(int nd, int l, int r, int x, int y, int v)
{
	int m = (l + r) / 2, res = 0;
	if (l == x && r == y)
	{
		if (mn[nd] > v) return 0;
		if (l == r) return l;
		if (mn[nd * 2] + f[nd] <= v) return find(nd  * 2, l, m, l, m, v - f[nd]);
		return find(nd * 2 + 1, m + 1, r, m + 1, r, v - f[nd]);
	}
	if (x <= m) res = find(nd * 2, l, m, x, min(y, m), v - f[nd]);
	if (res) return res;
	if (m < y) res = find(nd * 2 + 1, m + 1, r, max(x, m + 1), y, v - f[nd]);
	return res;
}

void add(int nd, int l, int r, int x, int y)
{
	if (l == x && r == y) f[nd]++, mn[nd]++;
	else
	{
		int m = (l + r) / 2;
		if (x <= m) add(nd * 2, l, m, x, min(y, m));
		if (m < y)
		{
			add(nd * 2 + 1, m + 1, r, max(x, m + 1), y);
			mn[nd] = mn[nd * 2 + 1] + f[nd];
		}
	}
}

long long calc(int nd, int l, int r)
{
	if (l == r)
		return f[nd] * (f[nd] - 1LL) / 2;
	int m = (l + r) / 2;
	f[nd * 2] += f[nd];
	f[nd * 2 + 1] += f[nd];
	return calc(nd * 2, l, m) + calc(nd * 2 + 1, m + 1, r);
}

int main()
{
	int n;
	cin >> n;
	vector<pair<int, int>> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i].first >> a[i].second;

	sort(a.begin(), a.end());
	int maxH = a[n - 1].first;
	for (auto [h, k] : a)
	{
		int v = get(1, 1, maxH, h - k + 1);
		int r = find(1, 1, maxH, 1, h, v - 1);
		if (!r) r = h + 1;
		else add(1, 1, maxH, r, h);
		k -= h - r + 1;
		int l = find(1, 1, maxH, 1, r - 1, v);
		add(1, 1, maxH, l, l + k - 1);
	}

	cout << calc(1, 1, maxH) << endl;
}

• 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