oj.uz

Submission #955229

# Submission time Handle Problem Language Result Execution time Memory
955229 2024-03-29T21:05:31 Z MinaRagy06 Pairs (IOI07_pairs) C++17
100 / 100
 257 ms 73912 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6680 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7260 KB Output is correct
2 Correct 12 ms 7516 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7772 KB Output is correct
2 Correct 15 ms 7772 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7772 KB Output is correct
2 Correct 17 ms 7772 KB Output is correct
3 Correct 15 ms 7772 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 11356 KB Output is correct
2 Correct 34 ms 11264 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 11544 KB Output is correct
2 Correct 51 ms 11716 KB Output is correct
3 Correct 51 ms 11760 KB Output is correct
4 Correct 49 ms 11524 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 14272 KB Output is correct
2 Correct 92 ms 14264 KB Output is correct
3 Correct 53 ms 12232 KB Output is correct
4 Correct 56 ms 11972 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 45404 KB Output is correct
2 Correct 15 ms 53792 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 28100 KB Output is correct
2 Correct 89 ms 28184 KB Output is correct
3 Correct 64 ms 28088 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 56764 KB Output is correct
2 Correct 185 ms 65976 KB Output is correct
3 Correct 80 ms 65984 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 65972 KB Output is correct
2 Correct 257 ms 73716 KB Output is correct
3 Correct 102 ms 73912 KB Output is correct