oj.uz

Submission #380641

# Submission time Handle Problem Language Result Execution time Memory
380641 2021-03-22T16:16:00 Z skittles1412 Pairs (IOI07_pairs) C++17
100 / 100
 644 ms 254572 KB 
#include "bits/stdc++.h"

using namespace std;

//sad; long long double doesn't exist
using ld = long double;

//imagine a language where int = long
#define long long long

//typing too hard
#define endl "\n"

#define sz(x) int((x).size())

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::failbit);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int n, b, d, _m;
	cin >> b >> n >> d >> _m;
	long ans = 0;
	if(b == 1) {
		int arr[n];
		for(int i = 0; i < n; i++) {
			cin >> arr[i];
		}
		sort(arr, arr + n);
		int j = 0;
		for(int i = 0; i < n; i++) {
			while(arr[i] - arr[j] > d) {
				j++;
			}
			ans += i - j;
		}
	}else if(b == 2) {
		const int am = 80000 * 1;
		const int m = 80000 * 3;
		pair<int, int> arr[n];
		for(int i = 0; i < n; i++) {
			int x, y;
			cin >> x >> y;
			arr[i].first = x + y + am;
			arr[i].second = x - y + am;
		}
		sort(arr, arr + n);
		int bit[m + 1]{};
		auto add = [&](int ind, int x) {
			ind++;
			while(ind <= m) {
				bit[ind] += x;
				ind += ind & -ind;
			}
		};
		auto psum = [&](int ind) {
			int ret = 0;
			while(ind > 0) {
				ret += bit[ind];
				ind -= ind & -ind;
			}
			return ret;
		};
		auto sum = [&](int l, int r) {
			return psum(min(m, r + 1)) - psum(max(0, l));
		};
		int j = 0;
		for(int i = 0; i < n; i++) {
			while(arr[i].first - arr[j].first > d) {
				add(arr[j].second, -1);
				j++;
			}
			ans += sum(arr[i].second - d, arr[i].second + d);
			add(arr[i].second, 1);
		}
	}else {
		const int am = 80 * 2;
		const int m = 80 * 5;
		array<int, 4> arr[n];
		for(int i = 0; i < n; i++) {
			int x, y, z;
			cin >> x >> y >> z;
			arr[i][0] = x + y + z + am;
			arr[i][1] = x + y - z + am;
			arr[i][2] = x - y + z + am;
			arr[i][3] = x - y - z + am;
		}
		sort(arr, arr + n);
		int bit[m + 1][m + 1][m + 1]{};
		auto add = [&](int _a, int _b, int _c, int x) {
			_a++;
			_b++;
			_c++;
			int a = _a;
			while(a <= m) {
				int b = _b;
				while(b <= m) {
					int c = _c;
					while(c <= m) {
						bit[a][b][c] += x;
						c += c & -c;
					}
					b += b & -b;
				}
				a += a & -a;
			}
		};
		auto psum = [&](int _a, int _b, int _c) {
			int ret = 0;
			int a = _a;
			while(a > 0) {
				int b = _b;
				while(b > 0) {
					int c = _c;
					while(c > 0) {
						ret += bit[a][b][c];
						c -= c & -c;
					}
					b -= b & -b;
				}
				a -= a & -a;
			}
			return ret;
		};
		auto sum = [&](int x1, int x2, int y1, int y2, int z1, int z2) {
			x1 = max(0, x1);
			y1 = max(0, y1);
			z1 = max(0, z1);
			x2 = min(m, x2 + 1);
			y2 = min(m, y2 + 1);
			z2 = min(m, z2 + 1);
			return +psum(x2, y2, z2)
				   - psum(x2, y2, z1)
				   - psum(x2, y1, z2)
				   - psum(x1, y2, z2)
				   + psum(x2, y1, z1)
				   + psum(x1, y2, z1)
				   + psum(x1, y1, z2)
				   - psum(x1, y1, z1);
		};
		int j = 0;
		for(int i = 0; i < n; i++) {
			while(arr[i][0] - arr[j][0] > d) {
				add(arr[j][1], arr[j][2], arr[j][3], -1);
				j++;
			}
			ans += sum(arr[i][1] - d, arr[i][1] + d, arr[i][2] - d, arr[i][2] + d, arr[i][3] - d, arr[i][3] + d);
			add(arr[i][1], arr[i][2], arr[i][3], 1);
		}
	}
	cout << ans << endl;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 748 KB Output is correct
2 Correct 14 ms 748 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 748 KB Output is correct
2 Correct 19 ms 748 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 748 KB Output is correct
2 Correct 20 ms 748 KB Output is correct
3 Correct 19 ms 748 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2028 KB Output is correct
2 Correct 31 ms 2028 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2028 KB Output is correct
2 Correct 35 ms 2156 KB Output is correct
3 Correct 34 ms 2028 KB Output is correct
4 Correct 33 ms 2028 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2028 KB Output is correct
2 Correct 36 ms 2028 KB Output is correct
3 Correct 39 ms 2028 KB Output is correct
4 Correct 36 ms 2028 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 252652 KB Output is correct
2 Correct 139 ms 252780 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 254316 KB Output is correct
2 Correct 280 ms 254316 KB Output is correct
3 Correct 258 ms 254316 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 254316 KB Output is correct
2 Correct 530 ms 254572 KB Output is correct
3 Correct 384 ms 254444 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 254216 KB Output is correct
2 Correct 644 ms 254572 KB Output is correct
3 Correct 433 ms 254572 KB Output is correct