Submission #1143064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143064		IBory	Pairs (IOI07_pairs)	C++20	100 / 100	231 ms	33864 KiB

pairs

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

const ll MAX = 100007, MAX3 = 200, INF = 1E9;
int Z[MAX3][MAX3][MAX3];

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 {
		vector<tuple<ll, ll, ll>> P(N);
		ll minY = 1E9, minZ = 1E9;
		for (auto& [x, y, z] : P) {
			ll a, b, c;
			cin >> a >> b >> c;
			x = a;
			y = b + c;
			z = b - c;
			minY = min(minY, y);
			minZ = min(minZ, z);
		}
		for (auto& [x, y, z] : P) {
			y = y - minY + 1;
			z = z - minZ + 1;
			Z[x][y][z]++;
		}

		for (int x = 0; x < MAX3; ++x) {
			for (int y = 0; y < MAX3; ++y) for (int z = 1; z < MAX3; ++z) Z[x][y][z] += Z[x][y][z - 1];
			for (int z = 0; z < MAX3; ++z) for (int y = 1; y < MAX3; ++y) Z[x][y][z] += Z[x][y - 1][z];
		}

		ll ans = 0;
		for (auto [x, y, z] : P) {
			for (int n = max(0LL, x - D); n <= min(MAX3 - 1, x + D); ++n) {
				ll d = D - abs(x - n);
				ll y1 = min(MAX3 - 1, y + d), y2 = max(0LL, y - d - 1);
				ll z1 = min(MAX3 - 1, z + d), z2 = max(0LL, z - d - 1);
				ans += Z[n][y1][z1] - Z[n][y2][z1] - Z[n][y1][z2] + Z[n][y2][z2];
				// cout << ans << ' ' << d << ' ' << y2 << ' ' << y1 << ' ' << z2 << ' ' << z1 << '\n';
			}
			// cout << '\n';
		}

		ans = (ans - N) / 2LL;
		cout << ans << '\n';
	}
	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: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10