#1184252 (C++23(gcc16)) No.3679 なんかでっかい虫リターンズ

• 問題: No.3679 なんかでっかい虫リターンズ
• ユーザー: kyoka3180
• 提出日時: 2026-09-06 11:48:50
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 20,202 bytes
• コンパイル時間: 4,351 ms
• コンパイル使用メモリ: 361,988 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-09-06 11:49:15
• 合計ジャッジ時間: 6,076 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 17

ソースコード

//https://zenn.dev/antyuntyun/articles/atcoder-cpp-template
#include <iostream>
#include <bits/stdc++.h>
#include <cassert>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;

// clang-format off
// cin cout の結びつけ解除, stdioと同期しない(入出力非同期化)
// cとstdの入出力を混在させるとバグるので注意
struct Fast {Fast() {std::cin.tie(0); ios::sync_with_stdio(false);}} fast;

/* alias */
using ull = unsigned long long;
using ll = long long;

/* vector */
template <class T> using vc = std::vector<T>;
template <class T> using vvc = std::vector<vc<T>>;
template <class T> using vvvc = std::vector<vvc<T>>;
template <class T> using vvvvc = std::vector<vvvc<T>>;

/* define short */
#define pb push_back
#define mp make_pair
#define all(obj) (obj).begin(), (obj).end()
#define YN(bool) if(bool){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}

/* REP macro */
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define rep(i, n) reps(i, 0, n)
#define rrep(i, n) reps(i, 1, n + 1)
#define repd(i,n) for(ll i=n-1;i>=0;i--)
#define rrepd(i,n) for(ll i=n;i>=1;i--)

/* debug */
// 標準エラー出力を含む提出はrejectされる場合もあるので注意
#define debug(x) cerr << "\033[33m(line:" << __LINE__ << ") " << #x << ": " << x << "\033[m" << endl;

/* func */
inline int in_int() {int x; cin >> x; return x;}
inline ll in_ll() {ll x; cin >> x; return x;}
inline string in_str() {string x; cin >> x; return x;}
template <typename T> inline void print(const vector<T>& v, string s = " ")
    {rep(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}
template <typename T, typename S> inline void print(const pair<T, S>& p)
    {cout << p.first << " " << p.second << endl;}
template <typename T> inline void print(const T& x) {cout << x << "\n";}
template <typename T, typename S> inline void print(const vector<pair<T, S>>& v)
    {for (auto&& p : v) print(p);}
// 第一引数と第二引数を比較し、第一引数(a)をより大きい/小さい値に上書き
template <typename T> inline bool chmin(T& a, const T& b) {bool compare = a > b; if (a > b) a = b; return compare;}
template <typename T> inline bool chmax(T& a, const T& b) {bool compare = a < b; if (a < b) a = b; return compare;}

ll MOD = 998244353;

ll powLL(ll a,ll n,bool isMOD){
    ll res = 1, tmp = a;
    while(n>0){
        if(n%2==1){
            res *= tmp;
            if(isMOD){
                res %= MOD;
            }
        }
        tmp = tmp * tmp;
        if(isMOD){
            tmp %= MOD;
        }
        n /= 2;
    }
    return res;
}

ll modinvLL(ll a, ll m) {
    return powLL(a, m - 2, m);
}

// modint -----------------------------------------------------
// AtCoderのmodintと同様の使い方ができるクラス
// 使用例:
//   using mint = ModInt<998244353>;
//   mint a = 10, b = 3;
//   mint c = a + b;         // 加算
//   mint d = a * b;         // 乗算
//   mint e = a / b;         // 除算 (mod逆元)
//   mint f = a.pow(100);    // べき乗
//   mint g = a.inv();       // 逆元
//   cout << c << endl;      // 出力
//   cin >> a;               // 入力
//   long long v = a.val();  // 値の取得
template <long long Mod>
class ModInt {
    long long _v;

    static long long mod_pow(long long a, long long n, long long m) {
        long long res = 1 % m;
        a %= m;
        if (a < 0) a += m;
        while (n > 0) {
            if (n & 1) res = res * a % m;
            a = a * a % m;
            n >>= 1;
        }
        return res;
    }

public:
    ModInt() : _v(0) {}
    ModInt(long long v) {
        long long x = v % Mod;
        if (x < 0) x += Mod;
        _v = x;
    }

    long long val() const { return _v; }
    static constexpr long long mod() { return Mod; }

    ModInt& operator+=(const ModInt& rhs) {
        _v += rhs._v;
        if (_v >= Mod) _v -= Mod;
        return *this;
    }
    ModInt& operator-=(const ModInt& rhs) {
        _v -= rhs._v;
        if (_v < 0) _v += Mod;
        return *this;
    }
    ModInt& operator*=(const ModInt& rhs) {
        _v = _v * rhs._v % Mod;
        return *this;
    }
    ModInt& operator/=(const ModInt& rhs) {
        return *this *= rhs.inv();
    }

    ModInt operator+() const { return *this; }
    ModInt operator-() const { return ModInt() - *this; }

    ModInt& operator++() {
        _v++;
        if (_v == Mod) _v = 0;
        return *this;
    }
    ModInt& operator--() {
        if (_v == 0) _v = Mod;
        _v--;
        return *this;
    }
    ModInt operator++(int) { ModInt res = *this; ++*this; return res; }
    ModInt operator--(int) { ModInt res = *this; --*this; return res; }

    friend ModInt operator+(ModInt a, const ModInt& b) { return a += b; }
    friend ModInt operator-(ModInt a, const ModInt& b) { return a -= b; }
    friend ModInt operator*(ModInt a, const ModInt& b) { return a *= b; }
    friend ModInt operator/(ModInt a, const ModInt& b) { return a /= b; }
    friend bool operator==(const ModInt& a, const ModInt& b) { return a._v == b._v; }
    friend bool operator!=(const ModInt& a, const ModInt& b) { return a._v != b._v; }

    ModInt pow(long long n) const {
        assert(n >= 0);
        return ModInt(mod_pow(_v, n, Mod));
    }
    // Modが素数である場合のみ使用可
    ModInt inv() const {
        assert(_v != 0);
        return ModInt(mod_pow(_v, Mod - 2, Mod));
    }

    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) {
        return os << x._v;
    }
    friend std::istream& operator>>(std::istream& is, ModInt& x) {
        long long v; is >> v;
        x = ModInt(v);
        return is;
    }
};

using mint998 = ModInt<998244353>;
using mint107 = ModInt<1000000007>;
// --------------------------------------------------------------

// sgment tree -----------------------------------------------
using SG = long long;

template <class S, S (*op)(S, S), S (*e)()>
struct segtree {
public:
    segtree() : segtree(0) {}
    explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
    explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = 0;
        while ((1 << log) < _n) log++;
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

// 2. 二項演算 (左右の値をどう合成するか)
SG op(SG a, SG b) {
    return min(a, b);
}

// 3. 単位元 (min演算なら、どんな値と比べても影響を与えない十分大きな値)
SG e() {
    return 1e18;
}

// lazy segment tree -----------------------------------------------
// AtCoderLibraryのlazy_segtreeと同様の使い方ができるクラス
// 使用例:
//   using LS = LazySegtree<S, op, e, F, mapping, composition, id>;
//   LS seg(n);              // 要素数nで初期化 (各要素はe())
//   LS seg(v);               // vector<S>で初期化
//   seg.set(p, x);           // p番目をxに更新
//   S x = seg.get(p);        // p番目を取得
//   S x = seg.prod(l, r);    // [l, r)の区間積を取得
//   S x = seg.all_prod();    // 全区間の積を取得
//   seg.apply(p, f);         // p番目にfを作用
//   seg.apply(l, r, f);      // [l, r)にfを作用
//   seg.max_right<pred>(l);  // pred(prod(l, r))==trueな最大のrを二分探索
//   seg.min_left<pred>(r);   // pred(prod(l, r))==trueな最小のlを二分探索
template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S),
          F (*composition)(F, F), F (*id)()>
struct LazySegtree {
public:
    LazySegtree() : LazySegtree(0) {}
    explicit LazySegtree(int n) : LazySegtree(std::vector<S>(n, e())) {}
    explicit LazySegtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = 0;
        while ((1 << log) < _n) log++;
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

// 2'. mapping (作用素fを値xに適用した結果を返す)
SG mapping(SG f, SG x) {
    return f == 1e18 ? x : f;
}

// 3'. composition (作用素fの後にgを合成した作用素を返す。g・f)
SG composition(SG f, SG g) {
    return f == 1e18 ? g : f;
}

// 4'. id (何もしない作用素の単位元)
SG id() {
    return 1e18;
}

// UnionFind (dsu) -----------------------------------------------
// AtCoderLibraryのdsuと同様の使い方ができるクラス
// 使用例:
//   dsu uf(n);                     // 要素数nで初期化 (各要素は自分自身の根)
//   uf.merge(a, b);                // aとbが属する集合を併合し、併合後の根を返す
//   bool ok = uf.same(a, b);       // aとbが同じ集合に属するか
//   int r = uf.leader(a);          // aが属する集合の根
//   int sz = uf.size(a);           // aが属する集合のサイズ
//   vector<vector<int>> g = uf.groups(); // 集合ごとに要素をまとめたリスト
struct dsu {
public:
    dsu() : _n(0) {}
    explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                            [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

private:
    int _n;
    std::vector<int> parent_or_size;
};

// SCC (強連結成分分解) -----------------------------------------------
// AtCoderLibraryのscc_graphと同様の使い方ができるクラス
// 使用例:
//   scc_graph g(n);                       // 頂点数nで初期化
//   g.add_edge(from, to);                 // 有向辺 from->to を追加
//   vvc<int> groups = g.scc();            // 強連結成分ごとに頂点をまとめたリスト
//                                          // (トポロジカル順: 根/入力側のSCCが先頭)
namespace internal_scc {

template <class E>
struct csr {
    std::vector<int> start;
    std::vector<E> elist;
    explicit csr(int n, const std::vector<std::pair<int, E>>& edges)
        : start(n + 1), elist(edges.size()) {
        for (auto& e : edges) start[e.first + 1]++;
        for (int i = 1; i <= n; i++) start[i] += start[i - 1];
        auto counter = start;
        for (auto& e : edges) elist[counter[e.first]++] = e.second;
    }
};

struct scc_graph_impl {
public:
    explicit scc_graph_impl(int n) : _n(n) {}

    int num_vertices() { return _n; }

    void add_edge(int from, int to) { edges.push_back({from, {to}}); }

    std::pair<int, std::vector<int>> scc_ids() {
        auto g = csr<edge>(_n, edges);
        int now_ord = 0, group_num = 0;
        std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);
        visited.reserve(_n);
        auto dfs = [&](auto self, int v) -> void {
            low[v] = ord[v] = now_ord++;
            visited.push_back(v);
            for (int i = g.start[v]; i < g.start[v + 1]; i++) {
                auto to = g.elist[i].to;
                if (ord[to] == -1) {
                    self(self, to);
                    low[v] = std::min(low[v], low[to]);
                } else {
                    low[v] = std::min(low[v], ord[to]);
                }
            }
            if (low[v] == ord[v]) {
                while (true) {
                    int u = visited.back();
                    visited.pop_back();
                    ord[u] = _n;
                    ids[u] = group_num;
                    if (u == v) break;
                }
                group_num++;
            }
        };
        for (int i = 0; i < _n; i++) {
            if (ord[i] == -1) dfs(dfs, i);
        }
        for (auto& x : ids) x = group_num - 1 - x;
        return {group_num, ids};
    }

    std::vector<std::vector<int>> scc() {
        auto [group_num, ids] = scc_ids();
        std::vector<int> counts(group_num);
        for (auto x : ids) counts[x]++;
        std::vector<std::vector<int>> groups(group_num);
        for (int i = 0; i < group_num; i++) groups[i].reserve(counts[i]);
        for (int i = 0; i < _n; i++) groups[ids[i]].push_back(i);
        return groups;
    }

private:
    struct edge {
        int to;
    };
    int _n;
    std::vector<std::pair<int, edge>> edges;
};

}  // namespace internal_scc

struct scc_graph {
public:
    scc_graph() : g(0) {}
    explicit scc_graph(int n) : g(n) {}

    void add_edge(int from, int to) {
        int n = g.num_vertices();
        assert(0 <= from && from < n);
        assert(0 <= to && to < n);
        g.add_edge(from, to);
    }

    std::vector<std::vector<int>> scc() { return g.scc(); }

private:
    internal_scc::scc_graph_impl g;
};
// --------------------------------------------------------------

// https://algo-logic.info/run-length/
/* encode: ランレングス圧縮を行う
*/
vector<pair<char, int>> encode(const string& str) {
    int n = (int)str.size();
    vector<pair<char, int>> ret;
    for (int l = 0; l < n;) {
        int r = l + 1;
        for (; r < n && str[l] == str[r]; r++) {};
        ret.push_back({str[l], r - l});
        l = r;
    }
    return ret;
}

/* decode: ランレングス圧縮の復元を行う
*/
string decode(const vector<pair<char, int>>& code) {
    string ret = "";
    for (auto p : code) {
        for (int i = 0; i < p.second; i++) {
            ret.push_back(p.first);
        }
    }
    return ret;
}

ll isqrt_newton(ll x) {
    if (x <= 0) return 0;
    // 初期値は適当で良いが、sqrt(x)に近いほど速い
    ll s = x;
    ll t = (s + x / s) / 2;
    while (t < s) {
        s = t;
        t = (s + x / s) / 2;
    }
    return s;
}

ll H,W,A,B,R1,R2,C1,C2,P,Q;
int solve(){
    cin >> H >> W >> A >> B >> R1 >> C1 >> R2 >> C2 >> P >> Q;
    ll ans = 1e10;
    reps(r,R1,R2+1)reps(c,C1,C2+1){
        chmin(ans,abs(A-r)+abs(B-c)+abs(r-P)+abs(c-Q));
    }
    cout << ans + abs(P-A) + abs(Q-B) << endl; 
    return 0;
}

int main(){
    cout << std::fixed << std::setprecision(15);
    ll t=1;
    // cin >> t;
    rep(i,t) solve();
}