Submission #1143057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143057		IBory	Pairs (IOI07_pairs)	C++20	60 / 100	109 ms	19232 KiB

pairs

#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int MAX = 100007, INF = 1E9;

struct BIT {
	ll T[MAX];
	void Update(int i, ll v) {
		for (; i < MAX; i += i & -i) T[i] += v;
	}
	ll Query(int L, int R) {
		ll ret = 0; L--;
		for (; R; R -= R & -R) ret += T[R];
		for (; L; L -= L & -L) ret -= T[L];
		return ret;
	}
} T;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	ll B, N, D, M;
	cin >> B >> N >> D >> M;

	if (B == 1) {
		vector<ll> S(N);
		for (ll& n : S) cin >> n;
		sort(S.begin(), S.end());

		ll ans = 0;
		for (ll n : S) ans += upper_bound(S.begin(), S.end(), n + D) - lower_bound(S.begin(), S.end(), n - D);
		ans = (ans - N) / 2LL;
		cout << ans << '\n';
	}
	else if (B == 2) {
		vector<pii> P(N);
		vector<ll> Y = {-INF, INF};
		for (auto& [x, y] : P) {
			ll a, b;
			cin >> a >> b;
			x = a + b;
			y = a - b;
			Y.push_back(y);
		}

		sort(Y.begin(), Y.end());
		Y.erase(unique(Y.begin(), Y.end()), Y.end());

		vector<tuple<ll, ll, ll, ll>> S;
		for (auto [x, y] : P) {
			S.emplace_back(x, 0, y, 0);
			S.emplace_back(x - D - 1, 1, y - D, y + D);
			S.emplace_back(x + D, 2, y - D, y + D);
		}
		sort(S.begin(), S.end());
		
		ll ans = 0;
		// 0: Point Update
		// 1: Range Minus
		// 2: Range Query
		for (auto [_, op, y1, y2] : S) {
			y1 = lower_bound(Y.begin(), Y.end(), y1) - Y.begin();
			if (op == 0) T.Update(y1, 1);
			else {
				y2 = (upper_bound(Y.begin(), Y.end(), y2) - Y.begin()) - 1;
				if (op == 1) ans -= T.Query(y1, y2);
				else ans += T.Query(y1, y2);
			}
		}

		ans = (ans - N) / 2LL;
		cout << ans << '\n';
	}
	else {

	}
	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10