Submission #841764

#	Time	Username	Problem	Language	Result	Execution time	Memory
841764		fanwen	Pairs (IOI07_pairs)	C++17	100 / 100	389 ms	112716 KiB

pairs

/**
 *      author : pham van sam 
 *      created : 02 September 2023 (Saturday)
 **/

#include <bits/stdc++.h>
 
using namespace std;
 
namespace SUB1 {
	void Main() {
		int n, d, m; cin >> n >> d >> m;
		vector <int> a(n);
		for (auto &x : a) cin >> x;
		sort(a.begin(), a.end());
		long long ans = 0;
		for (int i = 1, j = 0; i < n; ++i) {
			while(j < i and a[i] - a[j] > d) j++;
			ans += i - j;
		}
		cout << ans; exit(0);
	}
}

namespace SUB2 {
	template <class T> struct Fenwick_Tree {
		vector<T> bit;
		int n;
		Fenwick_Tree(int _n = 0) : n(_n), bit(_n + 5){}
		
		void clear() { fill(bit.begin(), bit.end(), T(0)); }
	
		void update(int u, T val) {
			for (; u <= n; u += u & -u) bit[u] += val;
		}
		
		T get(int u) {
			T ans = 0;
			for (; u; u -= u & -u) ans += bit[u];
			return ans; 
		}
		
		T get(int l, int r) {
			return get(r) - get(l - 1);
		}
	};

	void Main() {
		int n, d, m; cin >> m >> d >> n;
		Fenwick_Tree <int> bit(2 * n);
		vector<pair<int, int>> p;
		for (int i = 0; i < m; ++i) {
			int x, y; cin >> x >> y;
			p.emplace_back(x - y, x + y);
		}
		sort(p.begin(), p.end());
		int j = 0;
		long long ans = 0;
		for (int i = 0; i < m; ++i) {
			while(p[i].first - p[j].first > d) {
				bit.update(p[j++].second, -1);
			}
			ans += bit.get(max(p[i].second - d, 1), min(p[i].second + d, 2 * n));
			bit.update(p[i].second, 1);
		}
		cout << ans;
	}
}

namespace SUB3 {
	struct FenwickTree {
		vector<vector<vector<int>>> bit;
		int n;
		FenwickTree(int n = 0) : n(n) {
			bit.assign(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1)));
		}

		void update(int x, int y, int z, int d) {
			for (int i = x; i <= n; i += i & -i) {
				for (int j = y; j <= n; j += j & -j) {
					for (int k = z; k <= n; k += k & -k) {
						bit[i][j][k] += d;
					}
				}
			}
		}

		int get(int x, int y, int z) {
			int ans = 0;
			x = min(x, n), y = min(y, n), z = min(z, n);
			for (int i = x; i > 0; i -= i & -i) {
				for (int j = y; j > 0; j -= j & -j) {
					for (int k = z; k > 0; k -= k & -k) {
						ans += bit[i][j][k];
					}
				}
			}
			return ans;
		}

		int get(int x, int y, int z, int u, int v, int t) {
			return get(u, v, t)
				- get(x - 1, v, t)
				- get(u, y - 1, t)
				- get(u, v, z - 1)
				+ get(x - 1, y - 1, t)
				+ get(x - 1, v, z - 1)
				+ get(u, y - 1, z - 1)
				- get(x - 1, y - 1, z - 1);
		}
	};

	struct point {
		int a, b, c, d; 
		point (int a = 0, int b = 0, int c = 0, int d = 0) : a(a), b(b), c(c), d(d) {}

		bool operator < (const point &p) const  {
			return make_tuple(a, b, c, d) < make_tuple(p.a, p.b, p.c, p.d);
		}
	};
	void Main() {
		int m, d, n; cin >> m >> d >> n;
		vector <point> p;
		FenwickTree bit(4 * n);
		for (int i = 0; i < m; ++i) {
			int x, y, z; cin >> x >> y >> z;
			p.emplace_back(x + y + z, x - y + z + 2 * n, x + y - z + 2 * n, y + z - x + 2 * n);
		}
		sort(p.begin(), p.end());
		long long ans = 0;
		for (int i = 0, j = 0; i < m; ++i) {
			while(p[i].a - p[j].a > d) {
				bit.update(p[j].b, p[j].c, p[j].d, -1);
				j++;
			}
			ans += bit.get(p[i].b - d, p[i].c - d, p[i].d - d, 
						   p[i].b + d, p[i].c + d, p[i].d + d);
			bit.update(p[i].b, p[i].c, p[i].d, 1);
		}
		cout << ans;
	}
}

void you_make_it(void) {
    int b; cin >> b;
    if(b == 1) SUB1::Main();
	else if(b == 2) SUB2::Main();
	else SUB3::Main();
}
 
signed main() {
 
#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    auto start_time = chrono::steady_clock::now();
 
    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
 
    you_make_it();
 
    auto end_time = chrono::steady_clock::now();
 
    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
 
    return (0 ^ 0);
}
 
// Dream it. Wish it. Do it.

Compilation message (stderr)

pairs.cpp: In instantiation of 'SUB2::Fenwick_Tree<T>::Fenwick_Tree(int) [with T = int]':
pairs.cpp:50:31:   required from here
pairs.cpp:28:7: warning: 'SUB2::Fenwick_Tree<int>::n' will be initialized after [-Wreorder]
   28 |   int n;
      |       ^
pairs.cpp:27:13: warning:   'std::vector<int> SUB2::Fenwick_Tree<int>::bit' [-Wreorder]
   27 |   vector<T> bit;
      |             ^~~
pairs.cpp:29:3: warning:   when initialized here [-Wreorder]
   29 |   Fenwick_Tree(int _n = 0) : n(_n), bit(_n + 5){}
      |   ^~~~~~~~~~~~

• 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