Submission #1265897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265897		canhnam357	Sails (IOI07_sails)	C++20	100 / 100	128 ms	3720 KiB

sails

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define all(x) x.begin(), x.end()
int st[1 << 18] = {}, lz[1 << 18] = {}, st2[1 << 18] = {};
void down(int id)
{
	if (!lz[id]) return;
	lz[id << 1] += lz[id];
	lz[id << 1 | 1] += lz[id];
	st[id << 1] += lz[id];
	st[id << 1 | 1] += lz[id];
	st2[id << 1] += lz[id];
	st2[id << 1 | 1] += lz[id];
	lz[id] = 0;
}
void add_range(int u, int v, int val, int id = 1, int l = 1, int r = 1 << 17)
{
	if (l > r) return;
	if (r < u || l > v) return;
	if (l >= u && r <= v)
	{
		st[id] += val;
		st2[id] += val;
		lz[id] += val;
		return;
	}
	down(id);
	int mid = (l + r) >> 1;
	add_range(u, v, val, id << 1, l, mid);
	add_range(u, v, val, id << 1 | 1, mid + 1, r);
	st[id] = max(st[id << 1], st[id << 1 | 1]);
	st2[id] = min(st2[id << 1], st2[id << 1 | 1]);
}
int get(int pos, int id = 1, int l = 1, int r = 1 << 17)
{
	if (l == r) return st[id];
	down(id);
	int mid = (l + r) >> 1;
	if (pos <= mid) return get(pos, id << 1, l, mid);
	return get(pos, id << 1 | 1, mid + 1, r);
}
int find_left(int val, int id = 1, int l = 1, int r = 1 << 17)
{
	if (l == r) return l;
	down(id);
	int mid = (l + r) >> 1;
	if (st2[id << 1] <= val) return find_left(val, id << 1, l, mid);
	return find_left(val, id << 1 | 1, mid + 1, r);
}
void find_right(int val, int h, int& ans, int id = 1, int l = 1, int r = 1 << 17)
{
	if (ans != -1) return;
	if (l > h) return;
	if (l == r)
	{
		ans = l;
		return;
	}
	down(id);
	int mid = (l + r) >> 1;
	if (st[id << 1 | 1] >= val) find_right(val, h, ans, id << 1 | 1, mid + 1, r);
	if (st[id << 1] >= val) find_right(val, h, ans, id << 1, l, mid);
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<pair<int, int>> a;
	for (int i = 0; i < n; i++)
	{
		int h, k;
		cin >> h >> k;
		a.emplace_back(h, k);
	}
	sort(all(a));
	for (auto x : a)
	{
		int h = x.first, k = x.second;
		if (h == k) add_range(1, h, 1);//, cout << "FULL\n";
		else
		{
			if (get(h - k) != get(h - k + 1))
			{
				//cout << "ENOUGH\n";
				add_range(h - k + 1, h, 1);
			}
			else
			{
				int val = get(h - k + 1);
				int l = find_left(val);
				int r = -1;
				find_right(val, h, r);
				add_range(r + 1, h, 1);
				k -= h - r;
				add_range(l, l + k - 1, 1);
				//cout << l << ' ' << r << '\n';
			}
		}
		//for (int i = 1; i <= 5; i++) cout << get(i) << ' ';
		//cout << '\n';
	}
	long long ans = 0;
	for (int i = 1; i <= 100000; i++)
	{
		long long s = get(i);
		ans += s * (s - 1) / 2;
	}
	cout << ans;
	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