Submission #73367027

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vst = vector<string>;
using vvst = vector<vector<string>>;
using vbool = vector<bool>;
using vvbool = vector<vector<bool>>;
using vch = vector<char>;
using vvch = vector<vector<char>>;
using pll = pair<ll, ll>;
using stll = stack<ll>;
using stst = stack<string>;
using setll = set<ll>;
using sets = set<string>;
using mapll = map<ll, ll>;
const ll INF = 1e18;
const ll MOD = 998244353; // 問題に合わせて 1000000007 に変更
const double PI = acos(-1);
const ll dx[] = {0, 1, 0, -1};
const ll dy[] = {1, 0, -1, 0};
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)  // 0からn未満の繰り返し
#define rep2(i, a, n) for(ll i = a; i < (ll)(n); i++)  // aからn未満の繰り返し
#define rrep(i, n) for(ll i = (ll)(n) - 1; i >= 0; i--)  // n-1から0以上の繰り返し
#define rrep2(i, a, n) for(ll i = (ll)(n) - 1; i >= a; i--)  // n-1からa以上の繰り返し
#define all(v) (v).begin(), (v).end() // 小さい順にソート
#define rall(v) (v).rbegin(), (v).rend() //大きい順にソート
#define Yes(b) cout << ((b) ? "Yes" : "No") << endl

// 最小値・最大値の更新 (更新されたらtrueを返す)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

// 自動でMODをとる構造体
struct mint {
    ll x;
    // コンストラクタ
    mint(ll x = 0) : x((x % MOD + MOD) % MOD) {}

    // 単項演算子 -
    mint operator-() const { return mint(-x); }

    // 加算・減算・乗算・除算 (代入演算子)
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint& a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint& operator/=(const mint& a) {
        return *this *= a.inv();
    }

    // インクリメント・デクリメント
    mint& operator++() {
        if (++x >= MOD) x -= MOD;
        return *this;
    }
    mint operator++(int) {
        mint res = *this;
        ++*this;
        return res;
    }
    mint& operator--() {
        if (x == 0) x = MOD;
        x--;
        return *this;
    }
    mint operator--(int) {
        mint res = *this;
        --*this;
        return res;
    }

    // 累乗
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // 逆元
    mint inv() const {
        return pow(MOD - 2);
    }

    // フレンド関数: ll との計算 (左右どちらでも可)
    friend mint operator+(const mint& a, const mint& b) { return mint(a) += b; }
    friend mint operator-(const mint& a, const mint& b) { return mint(a) -= b; }
    friend mint operator*(const mint& a, const mint& b) { return mint(a) *= b; }
    friend mint operator/(const mint& a, const mint& b) { return mint(a) /= b; }
    
    // 比較演算子 (std::set や std::map で使用可能)
    // ll と比較する場合も、mod を取った後の値で比較されることに注意
    friend bool operator==(const mint& a, const mint& b) { return a.x == b.x; }
    friend bool operator!=(const mint& a, const mint& b) { return a.x != b.x; }
    friend bool operator<(const mint& a, const mint& b) { return a.x < b.x; }
    friend bool operator>(const mint& a, const mint& b) { return a.x > b.x; }
    friend bool operator<=(const mint& a, const mint& b) { return a.x <= b.x; }
    friend bool operator>=(const mint& a, const mint& b) { return a.x >= b.x; }

    // 入出力
    friend istream& operator>>(istream& is, mint& a) { return is >> a.x; }
    friend ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
};

// 最大公約数
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

// 最小公倍数 (オーバーフローに注意)
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

// 素因数分解 (O(sqrt(N)))
// 返り値: {素数, 指数} の map
mapll prime_factor(ll n) {
    mapll ret;
    for (ll i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1) ret[n] = 1;
    return ret;
}

// 組み合わせ計算 (nCr)
ll conbi(ll n, ll r) {
    if (r < 0 || r > n) return 0;
    if (r > n / 2) r = n - r;
    ll res = 1;
    for (ll i = 1; i <= r; ++i) {
        res = res * (n - i + 1) / i;
    }
    return res;
}

// 配列の中身を表示
template <typename T>
void print_vec(const T& v) {
    for (const auto& x : v) cout << x << " ";
    cout << endl;
}

// ベクトルの入力: cin >> v; で動く
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (T& in : v) is >> in;
    return is;
}

// ベクトルの出力: cout << v; で動く (スペース区切り)
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (ll i = 0; i < (int)v.size(); i++) {
        os << v[i] << (i + 1 != (int)v.size() ? " " : "");
    }
    return os;
}

// 2次元配列の cout 出力対応
template <typename T>
ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
    for (ll i = 0; i < v.size(); i++) {
        for (ll j = 0; j < v[i].size(); j++) {
            os << v[i][j] << (j == v[i].size() - 1 ? "" : " ");
        }
        if (i != v.size() - 1) os << endl; // 最後の行以外は改行
    }
    return os;
}

// セグメント木の作成
template <typename T>
class SegmentTree {
    // 演算関数の型エイリアス
    using F = function<T(T, T)>;

    ll size;      // 葉の数 (2のべき乗)
    vector<T> tree; // データを格納する配列
    F op;          // 区間クエリで使う演算 (min, max, sumなど)
    T e;           // 単位元 (演算に影響しない値)

public:
    // コンストラクタ
    SegmentTree(const vector<T>& v, F _op, T _e) : op(_op), e(_e) {
        ll n = v.size();
        size = 1;
        while (size < n) size *= 2; // 2のべき乗にする

        tree.assign(2 * size, e); // 単位元で初期化

        // 葉（最下段）に値をセット
        for (ll i = 0; i < n; i++) {
            tree[size + i] = v[i];
        }

        // 親に向かって構築 (1-indexed: 根は1)
        for (ll i = size - 1; i >= 1; i--) {
            tree[i] = op(tree[2 * i], tree[2 * i + 1]);
        }
    }

    // 1点更新: index番目の値をxに変更
    void update(ll index, T x) {
        index += size; // 葉のノード番号に変換
        tree[index] = x;
        
        // 親に向かって更新
        while (index > 1) {
            index /= 2;
            tree[index] = op(tree[2 * index], tree[2 * index + 1]);
        }
    }

    // 区間取得: [l, r) の演算結果を求める (半開区間)
    T query(ll l, ll r) {
        T res_l = e; // 左側の累積結果
        T res_r = e; // 右側の累積結果
        
        l += size; // 葉のインデックスへ
        r += size;

        while (l < r) {
            // 左端が右側の子なら、それを採用して右へシフト
            if (l % 2 == 1) {
                res_l = op(res_l, tree[l]);
                l++;
            }
            // 右端が右側の子なら、一つ左（左側の子）を採用
            if (r % 2 == 1) {
                r--;
                res_r = op(tree[r], res_r);
            }
            l /= 2;
            r /= 2;
        }
        return op(res_l, res_r);
    }
    
    // 特定の要素を取得 (デバッグ用など)
    T get(ll index) {
        return tree[size + index];
    }

    // セグメント木上の二分探索 (O(log N))
    // [l, n) の範囲で、check( query(l, i+1) ) が true になる「最初のインデックス i」を返す
    // 見つからない場合は -1 を返す
    // check: 条件判定関数 (例: [](T val){ return val >= 10; })
    ll find_first(ll l, const function<bool(T)>& check) {
        if (l < 0 || l >= size) return -1;
        T acc = e; // それまでの累積値
        return find_first_recurse(l, size, 1, 0, size, check, acc);
    }

private:
    // 再帰用関数
    // a, b: 探索したい範囲 [a, b) (今回は [l, size))
    // k: 現在のノード番号
    // l, r: 現在のノードがカバーする範囲 [l, r)
    // check: 判定関数
    // acc: これまでの累積値 (参照渡しで更新していく)
    ll find_first_recurse(ll a, ll b, ll k, ll l, ll r, const function<bool(T)>& check, T& acc) {
        // 1. 範囲外なら無視
        if (r <= a || b <= l) return -1;

        // 2. このノードの値を含めても条件を満たさないなら、
        //    この部分木には答えがないので、値をaccに統合してスキップ
        if (check(op(acc, tree[k])) == false) {
            acc = op(acc, tree[k]);
            return -1;
        }

        // 3. 葉に到達した場合、条件を満たす（2で弾かれていないため）のでインデックスを返す
        if (k >= size) {
            return k - size;
        }

        // 4. 子ノードを探索（左 -> 右 の順）
        ll vl = find_first_recurse(a, b, 2 * k, l, (l + r) / 2, check, acc);
        if (vl != -1) return vl; // 左で見つかればそれを返す
        
        return find_first_recurse(a, b, 2 * k + 1, (l + r) / 2, r, check, acc);
    }
};

/*
区間和の宣言
SegmentTree<long long> st_sum(v, [](long long a, long long b){ return a + b; }, 0);

区間最小値の宣言
SegmentTree<long long> st_min(v, [](long long a, long long b){ return min(a, b); }, INF);
*/

// ユニオンファインド
struct UnionFind {
    vector<int> par; // 親の番号
    
    // コンストラクタ
    UnionFind(ll N) : par(N) {
        for(ll i = 0; i < N; i++) par[i] = -1; // -1なら根。絶対値はサイズ
    }
    
    // 根を求める (経路圧縮)
    ll root(ll x) {
        if (par[x] < 0) return x;
        return par[x] = root(par[x]);
    }
    
    // x と y を結合する
    void unite(ll x, ll y) {
        ll rx = root(x);
        ll ry = root(y);
        if (rx == ry) return; // 同じグループなら何もしない
        // サイズが大きい方にマージする (高速化)
        if (par[rx] > par[ry]) swap(rx, ry); 
        par[rx] += par[ry]; // サイズを加算
        par[ry] = rx;       // ryの親をrxにする
    }
    
    // x と y が同じグループか判定
    bool same(ll x, ll y) {
        return root(x) == root(y);
    }
    
    // x が属するグループのサイズ
    ll size(ll x) {
        return -par[root(x)];
    }
};

/*
UnionFindの使い方
UnionFind uf(N);
uf.unite(0, 1); // 0と1をつなぐ
if(uf.same(0, 2)) { ... } // 判定
*/


// string型をvll型に変換
// 第一引数は文字列, 第二引数は底上げする定数(初期では a = 0と扱う)
vll string_to_vll(string s, ll up = 0){
    ll n = size(s);
    vll result(n);
    rep(i, n){
        result[i] = s[i] - 'a' + up;
    }
    return result;
}

// vll型をstring型に変換。
// 第一引数はvll, 第二引数は底を低くする定数(初期では a = 0と扱う)
string vll_to_string(vll v, ll down = 0){
    ll n = v.size();
    string s = "";
    s.reserve(n);
    rep(i, n){
        // 数値に対応する文字に変換 ('a' を基準にする場合)
        // 例: 0 -> 'a', 1 -> 'b'
        char c = 'a' + (v[i] - down);
        s += c;
    }
    return s;
}

// index が条件を満たすかどうか
bool isOK(ll &index, ll &key, vll &a) {
    if (a[index] >= key) return true;
    else return false;
}

// めぐる式二分探索
ll binary_search(ll &key, vll &a) {
    ll ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    ll ok = (ll)a.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
    
    // ok と ng のどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1) {
        ll mid = (ok + ng) / 2;

        if (isOK(mid, key, a)) ok = mid;
        else ng = mid;
    }
    return ok;
}

// --------------------------------------------------------

// ダイクストラ法
// graph: 隣接リスト。graph[u] = { {v, cost}, ... }
// start: 始点
// dist: 距離を格納する配列 (参照渡しで更新)
void dijkstra(const vector<vector<pll>>& graph, ll start, vll& dist) {
    dist.assign(graph.size(), INF);
    dist[start] = 0;
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    pq.push({0, start}); // {cost, v}

    while (!pq.empty()) {
        auto [d, v] = pq.top();
        pq.pop();

        if (d > dist[v]) continue;

        for (auto& edge : graph[v]) {
            ll to = edge.first;
            ll cost = edge.second;
            if (chmin(dist[to], dist[v] + cost)) {
                pq.push({dist[to], to});
            }
        }
    }
}

/*
使い方:
ll N, M; cin >> N >> M;
vector<vector<pll>> G(N);
rep(i, M) {
    ll u, v, w; cin >> u >> v >> w;
    u--; v--; // 0-indexed
    G[u].push_back({v, w});
    G[v].push_back({u, w}); // 無向グラフの場合
}
vll dist;
dijkstra(G, 0, dist);
*/

// -----------------------------------------------------------

// ワーシャルフロイド法
// dist[i][j] : iからjへの最短距離。初期値はINF (ただし dist[i][i] = 0)
void warshall_floyd(vvll& dist) {
    ll n = dist.size();
    rep(k, n) {
        rep(i, n) {
            rep(j, n) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    chmin(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

// ------------------------------------------------------------

// クラスカル法用の辺構造体
struct Edge {
    ll u, v, cost;
    // コストの小さい順にソートするための比較演算子
    bool operator<(const Edge& o) const {
        return cost < o.cost;
    }
};

// クラスカル法
// N: 頂点数
// edges: 辺のリスト (u, v, cost)
// 返り値: 最小全域木の総コスト
ll kruskal(int N, vector<Edge>& edges) {
    sort(all(edges)); // 辺をコスト順にソート
    UnionFind uf(N);  // 以前のテンプレートのUnionFindを使用
    ll sum = 0;

    for (const auto& e : edges) {
        if (!uf.same(e.u, e.v)) {
            uf.unite(e.u, e.v);
            sum += e.cost;
        }
    }
    return sum;
}

/* 使い方:
ll N, M; cin >> N >> M;
vector<Edge> edges;
rep(i, M) {
    ll u, v, w; cin >> u >> v >> w;
    u--; v--; // 0-indexed
    edges.push_back({u, v, w});
}
cout << kruskal(N, edges) << endl;
*/

// ------------------------------------------------------------

// プリム法
// graph: 隣接リスト。graph[u] = { {v, cost}, ... }
// 返り値: 最小全域木の総コスト
// ※頂点0を含む連結成分のMSTを求めます
ll prim(const vector<vector<pll>>& graph) {
    ll N = graph.size();
    ll sum = 0;
    vector<bool> visited(N, false);
    
    // {cost, v} のペア。コストが小さい順に取り出す
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    
    // 頂点0からスタート (コスト0)
    pq.push({0, 0}); 

    while (!pq.empty()) {
        auto [cost, u] = pq.top();
        pq.pop();

        // 既に木に含まれているならスキップ
        if (visited[u]) continue;

        // 木に含める
        visited[u] = true;
        sum += cost;

        // 隣接する頂点を候補に追加
        for (auto& edge : graph[u]) {
            ll v = edge.first;
            ll w = edge.second;
            if (!visited[v]) {
                pq.push({w, v});
            }
        }
    }
    return sum;
}

/* 使い方:
ll N, M; cin >> N >> M;
vector<vector<pll>> G(N);
rep(i, M) {
    ll u, v, w; cin >> u >> v >> w;
    u--; v--;
    G[u].push_back({v, w});
    G[v].push_back({u, w}); // 無向グラフ
}
cout << prim(G) << endl;
*/

// -----------------------------------------------------------

// 座標圧縮
// 元の値を座圧後の値(0-indexed)に変換する
// vals: 重複ありの座標リスト
// 返り値: 圧縮されたリスト (これを使って binary_search する)
template <typename T>
vector<T> compress(vector<T> &vals) {
    sort(all(vals));
    vals.erase(unique(all(vals)), vals.end());
    return vals;
}

// 値 x が座圧後の何番目かを返す (lower_bound)
template <typename T>
ll get_pos(const vector<T> &vals, T x) {
    return lower_bound(all(vals), x) - vals.begin();
}

/*
使い方:
vll A = {100, 2, 100, 50, 2};
vll vals = A; // コピー
compress(vals); // vals は {2, 50, 100} になる
rep(i, N) {
    cout << get_pos(vals, A[i]) << " "; // 2 -> 1, 0, 2, 1, 0
}
*/

// -------------------------------------------------------

// トポロジカルソート
// G: グラフ, N: 頂点数
// 返り値: ソートされた頂点リスト (閉路がある場合は空のvectorを返す)
vll topological_sort(const vector<vll> &G, ll N) {
    vll res;
    vll indegree(N, 0);
    rep(i, N) for (ll next : G[i]) indegree[next]++;
    
    queue<ll> q;
    rep(i, N) if (indegree[i] == 0) q.push(i);
    
    while (!q.empty()) {
        ll v = q.front(); q.pop();
        res.push_back(v);
        for (ll next : G[v]) {
            indegree[next]--;
            if (indegree[next] == 0) q.push(next);
        }
    }
    
    if (res.size() != (size_t)N) return {}; 
    return res;
}
// --------------------------------------------------------


// 幾何ライブラリ (2次元)
struct Point {
    double x, y;
    Point(double x=0, double y=0): x(x), y(y) {}
    
    // ベクトル演算
    Point operator+(const Point& a) const { return Point(x+a.x, y+a.y); }
    Point operator-(const Point& a) const { return Point(x-a.x, y-a.y); }
    Point operator*(double k) const { return Point(x*k, y*k); }
    
    // ノルム (大きさの2乗)
    double norm() const { return x*x + y*y; }
    // 大きさ
    double abs() const { return sqrt(norm()); }
    
    // 内積 (dot product)
    double dot(const Point& a) const { return x*a.x + y*a.y; }
    // 外積 (cross product) -> 平行四辺形の面積・回転方向判定
    double cross(const Point& a) const { return x*a.y - y*a.x; }
    
    // 比較演算子 (sort用: x座標優先)
    bool operator<(const Point& a) const {
        return x != a.x ? x < a.x : y < a.y;
    }
};

// 偏角ソートなどで使う出力
ostream& operator<<(ostream& os, const Point& p) {
    return os << "(" << p.x << ", " << p.y << ")";
}

// ランレングス圧縮 (Run-Length Encoding)
// 文字列 s を受け取り、{文字, 連続回数} のペアの配列を返す
// 例: "AABBBC" -> {{'A', 2}, {'B', 3}, {'C', 1}}
vector<pair<char, int>> rle(const string& s) {
    vector<pair<char, int>> res;
    ll n = s.size();
    for (ll i = 0; i < n;) {
        ll j = i + 1;
        while (j < n && s[i] == s[j]) j++;
        res.push_back({s[i], j - i});
        i = j;
    }
    return res;
}

// 数列用 (vector<long long> など) のオーバーロード
// 例: {1, 1, 2, 2, 2} -> {{1, 2}, {2, 3}}
template <typename T>
vector<pair<T, int>> rle(const vector<T>& v) {
    vector<pair<T, int>> res;
    ll n = v.size();
    for (ll i = 0; i < n;) {
        ll j = i + 1;
        while (j < n && v[i] == v[j]) j++;
        res.push_back({v[i], j - i});
        i = j;
    }
    return res;
}

/*
-------- アルゴリズムリスト -------------
----------------------------------------------



bit全探索
rep(bit, 1<<N){ // 2のN乗を表す
    ll A=0, B=0;
    rep(i, N){
        if(bit>>i & 1) A += K[i]; // 各ビットが0 or 1かを判定
        else B += K[i];
    }
}

--------------------------------------------------

vvll s;

//dfs (INF = wall)
void dfs(ll x, ll y, ll H, ll W, ll D){
    s[y][x] = D;
    rep(i, 4){
        ll nx = x + dx[i], ny = y + dy[i];
        if(ny < 0 || H <= ny || nx < 0 || W <= nx) continue;
        if(s[ny][nx] != INF  && D-1 > s[ny][nx]){
            dfs(nx, ny, H, W, D-1);
        }
    }
}

// bfs
queue<pair<ll, ll>> q;
    rep(i, H){
        string s_temp;
        cin >> s_temp;
        rep(j, W){
            if(s_temp[j] == 'H'){
                s[i][j] = D+1;
                q.push({i, j}); // 要素の挿入
            } 
            else if(s_temp[j] == '#') s[i][j] = INF;
        }
    }

while(!q.empty()){
        ll y = q.front().first, x = q.front().second; // 先端要素の取得
        q.pop(); // 先端要素を排除
        rep(i, 4){
            ll nx = x + dx[i], ny = y + dy[i];
            if(ny < 0 || H <= ny || nx < 0 || W <= nx) continue;
            if(s[ny][nx] != INF  && s[y][x]-1 > s[ny][nx]){
                q.push({ny, nx});
                s[ny][nx] = s[y][x] - 1;
            }
        }
    }

// 迷路BFS
// H, W, start_y, start_x, Grid(S) は定義済みとする
vvll dist(H, vll(W, -1));
queue<pair<ll, ll>> q;

dist[sy][sx] = 0;
q.push({sy, sx});

while (!q.empty()) {
    auto [y, x] = q.front(); q.pop();
    
    // 終了条件 (ゴールについた)
    if (y == gy && x == gx) break;

    rep(i, 4) {
        ll ny = y + dy[i];
        ll nx = x + dx[i];
        
        // 範囲外・壁・訪問済み チェック
        if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
        if (S[ny][nx] == '#') continue;
        if (dist[ny][nx] != -1) continue;
        
        dist[ny][nx] = dist[y][x] + 1;
        q.push({ny, nx});
    }
}
*/

/*
--------- 忘れそうな文法リスト -----------

グローバル変数で定義したvectorの中身を後から決める方法
vvll strength_list; //グローバル変数
strength_list.resize(N, vll(0)); //main関数内

-------------------------------------------

辞書(map)の使い方
mapll dict; //定義
dict.insert{(key, value})  // 挿入法一つ目
dist[key] = value  // 挿入法二つ目
dict.erase(key)  // 要素の削除法
Yes(dict.count(key))  // 検索法一つ目
Yes(dict.contains(key))  // 検索法二つ目
ll min_val = *dict.begin(); 最小値の取得方法
ll max_val = *dict.rbegin(); // 最大値の取得方法
for(auto temp : dict){
    cout << temp.first << " " << temp.second << endl  // 全要素の表示
}

---------------------------------------------

集合(set)の使い方
setll st;
st.insert(num)  // 挿入法
st.count(num)  // 検索法一つ目
st.contains(num)  // 検索法二つ目
ll min_val = *st.begin(); 最小値の取得方法
ll max_val = *st.rbegin(); // 最大値の取得方法
ll target = *st.lower_bound(num); // 二分探索(num以上の最小の要素)　(※endチェック必須！)
ll target = *st.upper_bound(num); // 二分探索(numを超えるの最小の要素)

// 二分探索 (※endチェック必須！)
auto it = st.lower_bound(num); // num以上のイテレータ
if (it != st.end()) {
    ll val = *it; // ここで初めて値を取り出す
} else {
    // num以上の値は存在しない場合の処理
}

st.erase(num)  // 要素の削除法

while(!st.empty()){ // 破壊的操作をする場合
    auto temp = A.front();
    cout << temp.first << " " << temp.second << endl  // 全要素の表示
    st.pop();
}

for(auto temp : st){ // 破壊的操作をしない場合
    cout << temp.first << " " << temp.second << endl  // 全要素の表示
}
A.size()  // 濃度の表示

二分探索 or 最大値 or 最小値 => set, multiset
自分でハッシュ関数を定義する場合 => unordered_set (平均O(1), 最悪O(N))

---------------------------------------------

vectorの二分探索
vll v = {1, 2, 5, 9, 20, 100};
ll key = 5;

// lower_bound (v[i] >= key と初めてなるようなイテレータを返す)
auto it_lower = lower_bound(all(v), key);
if (it_lower != v.end()) {
    cout << *it_lower << endl; // 値の表示(5)
} else {
    cout << "key以上の要素は存在しません" << endl; 
} 
cout << it_lower - v.begin() << endl; // 先頭からの距離を表示(2, 0-origin)
cout << v.end() - it_lower << endl; // 末尾までの距離を表示(4)

it_lower - v.begin() でvの要素でkey未満の値の個数が分かる。
v.end() - it_lower   でvの要素でkey以上の値の個数が分かる。

// upper_bound (v[i] > key と初めてなるようなイテレータを返す)
auto it_upper = upper_bound(all(v), key);
if (it_upper != v.end()) {
    cout << *it_upper << endl; // 値の表示(9)
} else {
    cout << "key以上の要素は存在しません" << endl; 
}  
cout << it_upper - v.begin() << endl; // 先頭からの距離を表示(3, 0-origin)
cout << v.end() - it_upper << endl; // 末尾までの距離を表示(3)

it_upper - v.begin() でvの要素でkey以下の値の個数が分かる。
v.end() - it_upper   でvの要素でkeyを超えるの値の個数が分かる。

it_upper - it_lower でkeyの値の要素の個数を求めることが可能。

--------------------------------------------------------

*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    // --- ここからコードを書く ---
    ll N, L, W, result = 0;
    cin >> N >> L >> W;
    rep(i, N){
        ll D;
        cin >> D;
        if(L - W <= D && D <= L + W){
            result++;
        }
    }
    cout << (result) << endl;;
    // ---------------------------
    return 0;
}

Submission Info

Judge Result