Submission #1049589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049589		Hacv16	Sails (IOI07_sails)	C++17	100 / 100	134 ms	6088 KiB

sails

#include <bits/stdc++.h>
using namespace std;

#define int long long int

const int MAX = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int H = 100010;

int n;
int seg[4 * H], lz[4 * H];

void refresh(int p, int l, int r)
{
	if(lz[p] == 0) return;

	int add = lz[p]; lz[p] = 0;
	seg[p] += add;

	if(l == r) return;

	int e = 2 * p, d = e + 1;
	lz[e] += add; lz[d] += add;
}

void update(int a, int b, int add, int p, int l, int r)
{
	refresh(p, l, r);

	if(a > r || b < l) return;
	if(a <= l && r <= b)
	{
		lz[p] += add;
		refresh(p, l, r);
		return;
	}

	int m = (l + r) >> 1, e = 2 * p, d = e + 1;
	update(a, b, add, e, l, m); update(a, b, add, d, m + 1, r);

	seg[p] = min(seg[e], seg[d]);
}

int query(int a, int b, int p, int l, int r)
{
	refresh(p, l, r);

	if(a > r || b < l) return INF;
	if(a <= l && r <= b) return seg[p];

	int m = (l + r) >> 1, e = 2 * p, d = e + 1;
	return min(query(a, b, e, l, m), query(a, b, d, m + 1, r));
}

int bb(int x, int p, int l, int r, bool equal)
{
	refresh(p, l, r);
	if(seg[p] > x || (seg[p] == x && !equal)) return -1;

	if(l == r) return l;
	int m = (l + r) >> 1, e = 2 * p, d = e + 1;

	refresh(e, l, m); refresh(d, m + 1, r);

	if(seg[e] < x || (equal && seg[e] == x)) return bb(x, e, l, m, equal);
	return bb(x, d, m + 1, r, equal);
}

int32_t main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;

	vector<pair<int, int>> sails;

	for(int i = 1; i <= n; i++)
	{
		int h, k; cin >> h >> k;
		sails.emplace_back(h, k);
	}

	sort(sails.begin(), sails.end());

	for(auto [h, k] : sails)
	{
		int val = query(h - k + 1, h - k + 1, 1, 1, H);
		int suffPos = bb(val, 1, 1, H, false);

		if(suffPos <= h && suffPos != -1)
		{
			update(suffPos, h, 1, 1, 1, H);
			k -= (h - suffPos + 1);
		}

		int prefPos = bb(val, 1, 1, H, true);
		assert(prefPos != -1);

		update(prefPos, prefPos + k - 1, 1, 1, 1, H);
	}

	int ans = 0;
	
	for(int i = 1; i < H; i++)
	{
		int curSails = query(i, i, 1, 1, H);
		ans += (curSails * (curSails - 1)) / 2;
	}

	cout << ans << '\n';
}

• 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