This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub SSRS-cp/cp_library
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_A" #include <bits/stdc++.h> using namespace std; #include "../../../data_structure/sequence/dual_invertible_binary_indexed_tree.hpp" int main(){ int N, T; cin >> N >> T; dual_invertible_binary_indexed_tree<int> BIT(T, plus<int>(), negate<int>(), 0); for (int i = 0; i < N; i++){ int l, r; cin >> l >> r; BIT.add(l, r, 1); } vector<int> S = BIT.get(); int ans = 0; for (int i = 0; i < T; i++){ ans = max(ans, S[i]); } cout << ans << endl; }
#line 1 "test/aoj/dsl/dsl_5_a_2.test.cpp" #define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_A" #include <bits/stdc++.h> using namespace std; #line 2 "data_structure/sequence/dual_invertible_binary_indexed_tree.hpp" /** * @brief 双対可逆 Binary Indexed Tree */ template <typename T> struct dual_invertible_binary_indexed_tree{ int N; vector<T> BIT; function<T(T, T)> f; function<T(T)> inv; T E; dual_invertible_binary_indexed_tree(){ } dual_invertible_binary_indexed_tree(int N, function<T(T, T)> f, function<T(T)> inv, T E): N(N), BIT(N + 1, E), f(f), inv(inv), E(E){ } dual_invertible_binary_indexed_tree(vector<T> &A, function<T(T, T)> f, function<T(T)> inv, T E): N(A.size()), BIT(N + 1), f(f), inv(inv), E(E){ for (int i = 0; i < N; i++){ BIT[i + 1] = A[i]; } } void add(int i, T x){ while (i > 0){ BIT[i] = f(BIT[i], x); i -= i & -i; } } void add(int l, int r, T x){ add(l, inv(x)); add(r, x); } T operator [](int i){ i++; T ans = E; while (i <= N){ ans = f(ans, BIT[i]); i += i & -i; } return ans; } vector<T> get(){ vector<T> ans = BIT; for (int i = N - 1; i >= 1; i--){ if (i + (i & -i) <= N){ ans[i] = f(ans[i + (i & -i)], ans[i]); } } ans.erase(ans.begin()); return ans; } }; #line 5 "test/aoj/dsl/dsl_5_a_2.test.cpp" int main(){ int N, T; cin >> N >> T; dual_invertible_binary_indexed_tree<int> BIT(T, plus<int>(), negate<int>(), 0); for (int i = 0; i < N; i++){ int l, r; cin >> l >> r; BIT.add(l, r, 1); } vector<int> S = BIT.get(); int ans = 0; for (int i = 0; i < T; i++){ ans = max(ans, S[i]); } cout << ans << endl; }