test/vector/inversion_number/aoj_alds1_5_d.test.cpp

• View this file on GitHub
• Last update: 2024-11-03 14:10:53+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_D

Depends on

• Fenwick Tree (Binary Indexed Tree) (src/datastructure/fenwick_tree.hpp)
• 座標圧縮 (src/vector/coordinate_compression.hpp)
• 転倒数 (src/vector/inversion_number.hpp)

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_D

#include "src/vector/inversion_number.hpp"

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int &e : a) cin >> e;
	cout << inversion_number(a) << endl;

	return 0;
}

#line 1 "test/vector/inversion_number/aoj_alds1_5_d.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_D

#line 1 "src/vector/inversion_number.hpp"



#line 1 "src/datastructure/fenwick_tree.hpp"



#include <vector>

template<class T>
class FenwickTree {
private:
	int n;
	std::vector<T> tree;

public:
	FenwickTree(int n) : n(n), tree(n) {}

	void add(int i, T x) {
		++i;
		while (i <= n) {
			tree[i - 1] += x;
			i += i & -i;
		}
	}

	T sum(int i) { // [0, i)
		T s{0};
		while (i > 0) {
			s += tree[i - 1];
			i -= i & -i;
		}
		return s;
	}

	T find(int l, int r) { // [l, r)
		return sum(r) - sum(l);
	}
};


#line 1 "src/vector/coordinate_compression.hpp"



#include <algorithm>
#line 6 "src/vector/coordinate_compression.hpp"

template<class T>
class CoordinateCompression {
private:
	std::vector<T> x;

public:
	CoordinateCompression(std::vector<T> const &v) : x(v.size()) {
		std::partial_sort_copy(v.begin(), v.end(), x.begin(), x.end());
		x.erase(std::unique(x.begin(), x.end()), x.end());
	}

	[[nodiscard]] int size() const { return x.size(); }

	T operator[](int k) { return x[k]; }

	[[nodiscard]] int get(T const &v) const {
		return std::lower_bound(x.begin(), x.end(), v) - x.begin();
	}
};


#line 6 "src/vector/inversion_number.hpp"

#line 8 "src/vector/inversion_number.hpp"

template<class T>
long long inversion_number(std::vector<T> const &v) {
	int const N = v.size();
	FenwickTree<int> ft(N);
	CoordinateCompression cc(v);
	long long res = 0;
	for (int i = 0; i < N; ++i) {
		int idx = cc.get(v[i]);
		res += i - ft.sum(idx);
		ft.add(idx, 1);
	}
	return res;
}


#line 4 "test/vector/inversion_number/aoj_alds1_5_d.test.cpp"

#include <iostream>
#line 7 "test/vector/inversion_number/aoj_alds1_5_d.test.cpp"

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int &e : a) cin >> e;
	cout << inversion_number(a) << endl;

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	13 ms	7 MB
g++	00_sample_01.in	AC	12 ms	7 MB
g++	01_small_00.in	AC	12 ms	7 MB
g++	01_small_01.in	AC	12 ms	7 MB
g++	01_small_02.in	AC	12 ms	7 MB
g++	01_small_03.in	AC	12 ms	7 MB
g++	02_rand_00.in	AC	12 ms	7 MB
g++	02_rand_01.in	AC	12 ms	7 MB
g++	02_rand_02.in	AC	12 ms	7 MB
g++	02_rand_03.in	AC	13 ms	7 MB
g++	02_rand_04.in	AC	12 ms	7 MB
g++	02_rand_05.in	AC	12 ms	7 MB
g++	02_rand_06.in	AC	12 ms	7 MB
g++	02_rand_07.in	AC	12 ms	7 MB
g++	03_corner_00.in	AC	12 ms	7 MB
g++	03_corner_01.in	AC	12 ms	7 MB
g++	03_corner_02.in	AC	12 ms	7 MB
g++	04_large_00.in	AC	75 ms	8 MB
g++	04_large_01.in	AC	76 ms	8 MB
g++	04_large_02.in	AC	76 ms	8 MB
g++	04_large_03.in	AC	76 ms	8 MB
g++	04_large_04.in	AC	77 ms	8 MB
g++	04_large_05.in	AC	79 ms	8 MB
g++	04_large_06.in	AC	92 ms	8 MB
g++	04_large_07.in	AC	92 ms	8 MB
g++	05_maximum_00.in	AC	182 ms	9 MB
g++	05_maximum_01.in	AC	145 ms	9 MB
g++	05_maximum_02.in	AC	148 ms	9 MB
g++	05_maximum_03.in	AC	145 ms	9 MB
g++	05_maximum_04.in	AC	161 ms	9 MB
clang++	00_sample_00.in	AC	11 ms	9 MB
clang++	00_sample_01.in	AC	11 ms	11 MB
clang++	01_small_00.in	AC	11 ms	9 MB
clang++	01_small_01.in	AC	11 ms	7 MB
clang++	01_small_02.in	AC	11 ms	11 MB
clang++	01_small_03.in	AC	11 ms	15 MB
clang++	02_rand_00.in	AC	11 ms	13 MB
clang++	02_rand_01.in	AC	11 ms	7 MB
clang++	02_rand_02.in	AC	11 ms	7 MB
clang++	02_rand_03.in	AC	11 ms	11 MB
clang++	02_rand_04.in	AC	11 ms	7 MB
clang++	02_rand_05.in	AC	11 ms	11 MB
clang++	02_rand_06.in	AC	11 ms	11 MB
clang++	02_rand_07.in	AC	11 ms	7 MB
clang++	03_corner_00.in	AC	11 ms	11 MB
clang++	03_corner_01.in	AC	11 ms	9 MB
clang++	03_corner_02.in	AC	11 ms	9 MB
clang++	04_large_00.in	AC	69 ms	13 MB
clang++	04_large_01.in	AC	70 ms	12 MB
clang++	04_large_02.in	AC	71 ms	17 MB
clang++	04_large_03.in	AC	70 ms	13 MB
clang++	04_large_04.in	AC	71 ms	15 MB
clang++	04_large_05.in	AC	75 ms	15 MB
clang++	04_large_06.in	AC	85 ms	11 MB
clang++	04_large_07.in	AC	90 ms	11 MB
clang++	05_maximum_00.in	AC	178 ms	16 MB
clang++	05_maximum_01.in	AC	138 ms	18 MB
clang++	05_maximum_02.in	AC	135 ms	14 MB
clang++	05_maximum_03.in	AC	134 ms	14 MB
clang++	05_maximum_04.in	AC	153 ms	10 MB

Back to top page