Submission #529346

#	Time	Username	Problem	Language	Result	Execution time	Memory
529346		sidon	Sails (IOI07_sails)	C++17	100 / 100	55 ms	2392 KiB

sails

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

const int Z = 1e5+3;

int N, F[Z];
int64_t ans;

void add(int i, int v) {
	for(; i < Z; i += i&-i) F[i] += v;
}

int get(int i) {
	int v = 0;
	for(; i > 0; i -= i&-i) v += F[i];
	return v;
}

int lowerBound(int v) {
	int i = 0;
	for(int j = 1<<17; j /= 2; )
		if(i + j < Z && F[i + j] < v) v -= F[i += j];
	return i + 1;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	cin >> N;

	array<int, 2> a[N];

	for(auto &[h, k] : a)
		cin >> h >> k;

	sort(a, a+N);

	for(auto &[h, k] : a) {
		int v = get(Z - h + k - 1);
		int l = lowerBound(v), r = lowerBound(v + 1) - 1;

		if(Z - h < l) {
			add(Z - h, 1);
			add(l, -1);
		}

		add(r - (k - max(0, l - (Z - h))) + 1, 1);
		add(r + 1, -1);
	}

	for(int i = 1; i < Z; ++i) {
		int64_t v = get(i);
		ans += v * (v - 1);
	}

	cout << (ans >> 1);
}

• 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