oj.uz

Submission #473755

# Submission time Handle Problem Language Result Execution time Memory
473755 2021-09-16T08:14:35 Z flashmt Sails (IOI07_sails) C++17
100 / 100
 177 ms 4256 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 268 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 4 ms 2252 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 920 KB Output is correct
2 Correct 41 ms 876 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1380 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 2264 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 3692 KB Output is correct
2 Correct 119 ms 3860 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 4036 KB Output is correct
2 Correct 101 ms 3760 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 4256 KB Output is correct
2 Correct 121 ms 2608 KB Output is correct