oj.uz

Submission #841761

# Submission time Handle Problem Language Result Execution time Memory
841761 2023-09-02T03:37:37 Z fanwen Pairs (IOI07_pairs) C++17
100 / 100
 383 ms 113480 KB 
/**
 *      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, x - y - z + 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

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.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 860 KB Output is correct
2 Correct 10 ms 856 KB Output is correct

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1496 KB Output is correct
2 Correct 18 ms 1500 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1496 KB Output is correct
2 Correct 23 ms 1500 KB Output is correct
3 Correct 23 ms 1500 KB Output is correct
4 Correct 22 ms 1496 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2008 KB Output is correct
2 Correct 25 ms 2008 KB Output is correct
3 Correct 25 ms 2008 KB Output is correct
4 Correct 25 ms 2008 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 110672 KB Output is correct
2 Correct 45 ms 110676 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 3532 KB Output is correct
2 Correct 37 ms 3536 KB Output is correct
3 Correct 29 ms 3536 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 60100 KB Output is correct
2 Correct 196 ms 60104 KB Output is correct
3 Correct 83 ms 60220 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 113480 KB Output is correct
2 Correct 383 ms 113404 KB Output is correct
3 Correct 144 ms 113480 KB Output is correct