제출 #955229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
955229		MinaRagy06	Pairs (IOI07_pairs)	C++17	100 / 100	257 ms	73912 KiB

pairs

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz(x) (int) x.size()

int n, d, m;
namespace _1d {
ll solve() {
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	int l = 0, r = -1;
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		while (r + 1 < n && a[r + 1] <= a[i] + d) {
			r++;
		}
		while (a[l] < a[i] - d) {
			l++;
		}
		ans += r - l + 1;
	}
	return (ans - n) / 2;
}
}

namespace _2d {

const int N = 100'005;
vector<int> gud[N];
vector<array<int, 2>> ask[N];
int bit[N];
void add(int x, int v) {
// 	cout << "upd " << x << ' ' << v << '\n';
	for (int i = x; i < N; i = (i | (i + 1))) {
		bit[i] += v;
	}
}
int get(int r) {
	if (r < 0) return 0;
	int ans = 0;
	for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
		ans += bit[i];
// 		cout << bit[i] << '\n';
	}
	return ans;
}
int get(int l, int r) {
	if (l > r) return 0;
// 	cout << "? " << l << ' ' << r << ": " << get(r) << ' ' << get(l - 1) << '\n';
	return get(r) - get(l - 1);
}

ll solve() {
	array<int, 2> a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i][0] >> a[i][1];
	}
	array<int, 2> v[n];
	vector<int> vals[2];
	for (int i = 0; i < n; i++) {
		v[i][0] = a[i][0] + a[i][1];
		v[i][1] = - a[i][0] + a[i][1];
		for (int k = 0; k < 2; k++) {
			vals[k].push_back(v[i][k]);
		}
	}
	for (int k = 0; k < 2; k++) {
		sort(vals[k].begin(), vals[k].end());
		vals[k].resize(unique(vals[k].begin(), vals[k].end()) - vals[k].begin());
	}
	for (int i = 0; i < n; i++) {
		array<int, 2> x;
		int y;
		for (int k = 1; k < 2; k++) {
			int s = lower_bound(vals[k].begin(), vals[k].end(), v[i][k] - d) - vals[k].begin();
			int e = lower_bound(vals[k].begin(), vals[k].end(), v[i][k] + d + 1) - vals[k].begin() - 1;
			x = {s, e};
			int p = lower_bound(vals[k].begin(), vals[k].end(), v[i][k]) - vals[k].begin();
			y = p;
		}
		int p = lower_bound(vals[0].begin(), vals[0].end(), v[i][0]) - vals[0].begin();
		ask[p].push_back(x);
		gud[p].push_back(y);
	}
	int l = 0, r = -1;
	ll ans = 0;
	for (int i = 0; i < sz(vals[0]); i++) {
		while (r + 1 < sz(vals[0]) && vals[0][r + 1] <= vals[0][i] + d) {
			r++;
			for (auto x : gud[r]) {
				add(x, 1);
			}
		}
		while (vals[0][l] < vals[0][i] - d) {
			for (auto x : gud[l]) {
				add(x, -1);
			}
			l++;
		}
		for (auto v1 : ask[i]) {
			ans += get(v1[0], v1[1]);
		}
	}
	return (ans - n) / 2;
}
}

namespace _3d {
const int N = 255;
vector<array<int, 3>> gud[N];
vector<array<array<int, 2>, 3>> ask[N];
int bit[N][N][N];
void add(int x, int y, int z, int v) {
	for (int i = x; i < N; i = (i | (i + 1))) {
		for (int j = y; j < N; j = (j | (j + 1))) {
			for (int k = z; k < N; k = ((k | (k + 1)))) {
				bit[i][j][k] += v;
			}
		}
	}
}
int get(int x, int y, int z) {
	if (x < 0 || y < 0 || z < 0) return 0;
	int ans = 0;
	for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
		for (int j = y; j >= 0; j = (j & (j + 1)) - 1) {
			for (int k = z; k >= 0; k = (k & (k + 1)) - 1) {
				ans += bit[i][j][k];
			}
		}
	}
	return ans;
}
int get(int l1, int r1, int l2, int r2, int l3, int r3) {
	if (l1 > r1 || l2 > r2 || l3 > r3) return 0;
	int ans = get(r1, r2, r3) - get(l1 - 1, r2, r3) - get(r1, l2 - 1, r3) - get(r1, r2, l3 - 1)
		    + get(l1 - 1, l2 - 1, r3) + get(l1 - 1, r2, l3 - 1) + get(r1, l2 - 1, l3 - 1) - get(l1 - 1, l2 - 1, l3 - 1);
	return ans;
}
ll solve() {
	array<int, 3> a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2];
	}
	array<int, 4> v[n];
	vector<int> vals[4];
	for (int i = 0; i < n; i++) {
		v[i][0] = a[i][0] + a[i][1] + a[i][2];
		v[i][1] = - a[i][0] + a[i][1] + a[i][2];
		v[i][2] = a[i][0] - a[i][1] + a[i][2];
		v[i][3] = - a[i][0] - a[i][1] + a[i][2];
		for (int k = 0; k < 4; k++) {
			vals[k].push_back(v[i][k]);
		}
	}
	for (int k = 0; k < 4; k++) {
		sort(vals[k].begin(), vals[k].end());
		vals[k].resize(unique(vals[k].begin(), vals[k].end()) - vals[k].begin());
	}
	for (int i = 0; i < n; i++) {
		array<array<int, 2>, 3> x;
		array<int, 3> y;
		for (int k = 1; k < 4; k++) {
			int s = lower_bound(vals[k].begin(), vals[k].end(), v[i][k] - d) - vals[k].begin();
			int e = lower_bound(vals[k].begin(), vals[k].end(), v[i][k] + d + 1) - vals[k].begin() - 1;
			x[k - 1] = {s, e};
			int p = lower_bound(vals[k].begin(), vals[k].end(), v[i][k]) - vals[k].begin();
			y[k - 1] = p;
		}
		int p = lower_bound(vals[0].begin(), vals[0].end(), v[i][0]) - vals[0].begin();
		ask[p].push_back(x);
		gud[p].push_back(y);
	}
	int l = 0, r = -1;
	ll ans = 0;
	for (int i = 0; i < sz(vals[0]); i++) {
		while (r + 1 < sz(vals[0]) && vals[0][r + 1] <= vals[0][i] + d) {
			r++;
			for (auto [x, y, z] : gud[r]) {
				add(x, y, z, 1);
			}
		}
		while (vals[0][l] < vals[0][i] - d) {
			for (auto [x, y, z] : gud[l]) {
				add(x, y, z, -1);
			}
			l++;
		}
		for (auto [v1, v2, v3] : ask[i]) {
			ans += get(v1[0], v1[1], v2[0], v2[1], v3[0], v3[1]);
		}
	}
	return (ans - n) / 2;
}
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int b;
	cin >> b;
	cin >> n >> d >> m;
	if (b == 1) {
		cout << _1d::solve() << '\n';
	} else if (b == 2) {
		cout << _2d::solve() << '\n';
	} else {
		cout << _3d::solve() << '\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