This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub kmyk/competitive-programming-library
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B"
#include "../utils/binary_search.hpp"
#include "../utils/binary_search_max.hpp"
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>
#include "../utils/macros.hpp"
using namespace std;
int main() {
int n; cin >> n;
vector<int> s(n);
REP (i, n) {
cin >> s[i];
}
int q; cin >> q;
int64_t cnt = 0;
while (q --) {
int t_i; cin >> t_i;
int l = binsearch(0, n, [&](int i) {
return s[i] >= t_i;
});
cnt += (l < n and s[l] == t_i);
int r = binsearch_max(0, n, [&](int i) {
return s[i] <= t_i;
});
assert ((l < n and s[l] == t_i) == (l <= r));
}
cout << cnt << endl;
return 0;
}
#line 1 "utils/binary_search.aoj.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B"
#line 2 "utils/binary_search.hpp"
#include <cassert>
#include <cstdint>
/**
* @brief a binary search / 二分探索
* @param[in] p a monotone predicate defined on $[l, r)$
* @return $\min \lbrace x \in [l, r) \mid p(x) \rbrace$, or r if it doesn't exist
*/
template <typename UnaryPredicate>
int64_t binsearch(int64_t l, int64_t r, UnaryPredicate p) {
assert (l <= r);
-- l;
while (r - l > 1) {
int64_t m = l + (r - l) / 2;
(p(m) ? r : l) = m;
}
return r;
}
#line 4 "utils/binary_search_max.hpp"
/**
* @return $\max \lbrace x \in (l, r] \mid p(x) \rbrace$, or l if it doesn't exist
*/
template <typename UnaryPredicate>
int64_t binsearch_max(int64_t l, int64_t r, UnaryPredicate p) {
assert (l <= r);
++ r;
while (r - l > 1) {
int64_t m = l + (r - l) / 2;
(p(m) ? l : r) = m;
}
return l;
}
#line 4 "utils/binary_search.aoj.test.cpp"
#line 7 "utils/binary_search.aoj.test.cpp"
#include <iostream>
#include <vector>
#line 2 "utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#line 10 "utils/binary_search.aoj.test.cpp"
using namespace std;
int main() {
int n; cin >> n;
vector<int> s(n);
REP (i, n) {
cin >> s[i];
}
int q; cin >> q;
int64_t cnt = 0;
while (q --) {
int t_i; cin >> t_i;
int l = binsearch(0, n, [&](int i) {
return s[i] >= t_i;
});
cnt += (l < n and s[l] == t_i);
int r = binsearch_max(0, n, [&](int i) {
return s[i] <= t_i;
});
assert ((l < n and s[l] == t_i) == (l <= r));
}
cout << cnt << endl;
return 0;
}