test/ARC075-E.test.cpp

View this file on GitHub
Last update: 2023-01-30 11:10:28+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
Link: https://atcoder.jp/contests/arc075/submissions/38473188

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A" 

#include "../src/dataStructure/fenwick_multiset.hpp"
#include "../src/template/accum1d.hpp"
#include "../src/algorithm/compression.hpp"

#include <iostream>
#include <vector>

int main() {
	// int N, K; std::cin >> N >> K;
	// std::vector<long long> a(N);
	// for (auto& ai : a) {
	// 	std::cin >> ai;
	// 	ai -= K;
	// }
	// zawa::accum1d S(a);
	// zawa::compression comp(S);
	// zawa::fenwick_multiset<int> set(comp.size());
	// long long ans = 0LL;
	// for (auto s : S) {
	// 	ans += set.count(0, comp[s] + 1);
	// 	set.insert(comp[s]);
	// }
	// std::cout << ans << std::endl;
	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Regular Contest 075
 * https://atcoder.jp/contests/arc075/submissions/38473188
 */

#line 1 "test/ARC075-E.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A" 

#line 2 "src/dataStructure/fenwick_multiset.hpp"

#line 2 "src/utility/fenwick_tree/add.hpp"

namespace zawa {

template <class dat_type>
struct add_structure {
	using T = dat_type;
	static constexpr T id = T{};
	static T add(const T& a, const T& b) {
		return a + b;
	}
	static T inverse(const T& a) {
		return -a;
	}
};

} // namespace zawa
#line 2 "src/dataStructure/fenwick_tree.hpp"

#include <vector>

namespace zawa {

template <class structure>
class fenwick_tree {
private:
	using T = typename structure::T;
	std::vector<T> dat;
	int pow_two;

	inline int lsb(int x) {
		return x & -x;
	}

	T sum(int r) {
		T res = 0;
		while (r > 0) {
			res = structure::add(res, dat[r]);
			r -= lsb(r);
		}
		return res;
	}
	
public:

	fenwick_tree(std::size_t n) : dat(n + 1, structure::id), pow_two(std::__lg(n) + 1) {}
	
	fenwick_tree(const std::vector<T>& A) : dat(A.size() + 1, structure::id), pow_two(std::__lg(A.size()) + 1) {
		for (int i = 0 ; i < (int)A.size() ; i++) {
			add(i, A[i]);
		}
	}


	T sum(int l, int r) {
		return structure::add(sum(r), structure::inverse(sum(l)));
	}

	void add(int pos, const T& v) {
		pos++;
		while (pos < (int)dat.size()) {
			dat[pos] = structure::add(dat[pos], v);
			pos += lsb(pos);
		}
	}

	int lower_bound(T val) {
		int res = 0;
		T now = structure::id;
		for (int x = (1 << pow_two) ; x > 0 ; x >>= 1) {
			if (res + x < (int)dat.size()) {
				T nxt = structure::add(now, dat[res + x]);
				if (nxt < val) {
					res += x;
					now = nxt;
				}
			}
		}
		return res;
	}
};

} // namespace zawa
#line 5 "src/dataStructure/fenwick_multiset.hpp"

#line 7 "src/dataStructure/fenwick_multiset.hpp"
#include <algorithm>

namespace zawa {

template <class T>
class fenwick_multiset {
private:
	std::vector<T> dat;
	fenwick_tree<add_structure<T>> fen;

public:

	fenwick_multiset(std::size_t n) : dat(n), fen(n) {}

	T count(int x) {
		return dat[x];
	}

	T count(int l, int r) {
		return fen.sum(l, r);
	}

	void insert(int x) {
		dat[x] += 1;
		fen.add(x, 1);
	}

	void insert(int x, const T& cnt) {
		dat[x] += cnt;
		fen.add(x, cnt);
	}

	T erase(int x) {
		if (dat[x]) {
			dat[x] -= 1;
			fen.add(x, -1);
			return 1;
		}
		else {
			return 0;
		}
	}

	T erase(int x, const T& cnt) {
		T res = std::min(dat[x], cnt);	
		dat[x] -= res;
		fen.add(x, -res);
		return res;
	}

	int kth_element(const T& k) {
		return fen.lower_bound(k);
	}
};

} // namespace zawa
#line 2 "src/template/accum1d.hpp"

#line 4 "src/template/accum1d.hpp"
#include <numeric>

namespace zawa {

template <class T>
struct accum1d : std::vector<T> {
	using vector = std::vector<T>;
	accum1d() {
		(*this).push_back(T());
	}
	accum1d(const std::vector<T>& A) {
		(*this).push_back(T());
		std::partial_sum(A.begin(), A.end(), std::back_inserter(*this));
	}	
	template <class InputIterator>
	accum1d(InputIterator begin, InputIterator end) {
		(*this).push_back(T());
		std::partial_sum(begin, end, std::back_inserter(*this));
	}
	T sum(std::size_t l, std::size_t r) {
		return (*this)[r] - (*this)[l];
	}
};

} // namespace zawa
#line 2 "src/algorithm/compression.hpp"

#line 5 "src/algorithm/compression.hpp"

namespace zawa {

template <class T>
class compression {
private:
	std::vector<T> as;
	std::vector<T> uniqued;

public:
	compression(const std::vector<T>& as) : as(as), uniqued(as) {
		std::sort(uniqued.begin(), uniqued.end());
		uniqued.erase(std::unique(uniqued.begin(), uniqued.end()), uniqued.end());
	}

	int operator[](const T& val) {
		return std::lower_bound(uniqued.begin(), uniqued.end(), val) - uniqued.begin();
	}

	int get(std::size_t i) {
		return (*this)[as[i]];
	}

	std::size_t size() {
		return uniqued.size();
	}
};

} // namespace zawa
#line 6 "test/ARC075-E.test.cpp"

#include <iostream>
#line 9 "test/ARC075-E.test.cpp"

int main() {
	// int N, K; std::cin >> N >> K;
	// std::vector<long long> a(N);
	// for (auto& ai : a) {
	// 	std::cin >> ai;
	// 	ai -= K;
	// }
	// zawa::accum1d S(a);
	// zawa::compression comp(S);
	// zawa::fenwick_multiset<int> set(comp.size());
	// long long ans = 0LL;
	// for (auto s : S) {
	// 	ans += set.count(0, comp[s] + 1);
	// 	set.insert(comp[s]);
	// }
	// std::cout << ans << std::endl;
	std::cout << "Hello World" << std::endl;
}

/*
 * AtCoder Regular Contest 075
 * https://atcoder.jp/contests/arc075/submissions/38473188
 */