verify/Algorithm_bisect_min_left.test.cpp

View this file on GitHub
Last update: 2025-01-11 20:21:43+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=ja

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=ja"
#include "../Utility/template.hpp"
#include "../Algorithm/bisect.hpp"

int main() {
    ll n;
    cin >> n;
    vector<ll> S(n);
    rep(i, 0, n) cin >> S[i];
    ll q;
    cin >> q;
    ll ans = 0;
    while(q--) {
        ll x;
        cin >> x;

        auto pred = [&](ll v) {
            return S[v] >= x;
        };

        auto l = min_left(0LL, n, pred);
        if(l == n || S[l] != x) {
        }
        else {
            ans++;
        }
    }
    cout << ans << endl;
}

#line 1 "verify/Algorithm_bisect_min_left.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=ja"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Algorithm/bisect.hpp"

template <typename T, typename F> T max_right(T l, T max_r_plus_one, F pred) {
    assert(l < max_r_plus_one);

    if (!pred(l)) return l;

    while (max_r_plus_one > l + 1) {
        T mid = ((l ^ max_r_plus_one) >> 1) + (l & max_r_plus_one);
        (pred(mid) ? l : max_r_plus_one) = mid;
    }
    return max_r_plus_one;
};

template <typename T, typename F> T min_left(T min_l, T r, F pred) {
    assert(min_l < r);

    if (pred(min_l)) return min_l;

    while (r > min_l + 1) {
        T mid = ((min_l ^ r) >> 1) + (min_l & r);
        (pred(mid) ? r : min_l) = mid;
    }
    return r;
}
/*
@brief 抽象化二分探索
@docs doc/bisect.md
*/
#line 4 "verify/Algorithm_bisect_min_left.test.cpp"

int main() {
    ll n;
    cin >> n;
    vector<ll> S(n);
    rep(i, 0, n) cin >> S[i];
    ll q;
    cin >> q;
    ll ans = 0;
    while(q--) {
        ll x;
        cin >> x;

        auto pred = [&](ll v) {
            return S[v] >= x;
        };

        auto l = min_left(0LL, n, pred);
        if(l == n || S[l] != x) {
        }
        else {
            ans++;
        }
    }
    cout << ans << endl;
}