oj.uz

Submission #1049589

# Submission time Handle Problem Language Result Execution time Memory
1049589 2024-08-09T00:19:35 Z Hacv16 Sails (IOI07_sails) C++17
100 / 100
 134 ms 6088 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 344 KB Output is correct
2 Correct 15 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 348 KB Output is correct
2 Correct 14 ms 520 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 348 KB Output is correct
2 Correct 14 ms 344 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 348 KB Output is correct
2 Correct 15 ms 592 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 604 KB Output is correct
2 Correct 18 ms 4584 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1884 KB Output is correct
2 Correct 48 ms 1244 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2172 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 3412 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 5824 KB Output is correct
2 Correct 98 ms 5832 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 6088 KB Output is correct
2 Correct 77 ms 5092 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 6088 KB Output is correct
2 Correct 101 ms 3452 KB Output is correct