Submission #63043709

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int) (x).size())
#define pb push_back
#define mp make_pair
#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll mod = 998244353;
const ll base = 1e6 + 9;
const ll inf = 1e18;
const int MAX = 5e5 + 42;
const int LG = 20;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

int ans[MAX];
vector<pii> have[MAX];

struct DSU {
    int n;
    vector<int> p, siz;
    vector<set<int>> comp;

    DSU(int N) {
        n = N - 1;
        p = vector<int>(n + 1);
        siz = vector<int>(n + 1);
        comp = vector<set<int>>(n + 1);
    };

    void create(int x) {
        p[x] = x;
        siz[x] = 1;
        comp[x] = {x};
    }

    void init() {
        for(int v = 1; v <= n; v++) create(v);
    }

    int get(int x) {
        return p[x] = (p[x] == x? x : get(p[x]));
    }

    bool unite(int x, int y, int w) {
        x = get(x), y = get(y);
        if(x == y) return 0;
        if(siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        p[y] = x;
        for(auto v : comp[y]) {
            for(auto [u, i] : have[v]) {
                if(comp[x].count(u)) {
                    ans[i] = w;
                }
            }
        }
        for(auto v : comp[y]) comp[x].insert(v);
        comp[y].clear();
        return 1;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for(auto &i : a) {
        for(auto &j : i) {
            cin >> j;
        }
    }
    vector<vector<pii>> val(1000010);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            val[a[i][j]].pb({i, j});
        }
    }

    auto idx = [&](int i, int j) {
        return i * m + j + 1;
    };

    int q;
    cin >> q;
    vector<array<int, 6>> qr(q);
    int IDX = 0;
    for(auto &[a, b, y, c, d, z] : qr) {
        cin >> a >> b >> y >> c >> d >> z;
        a--, b--, c--, d--;
        int u = idx(a, b);
        int v = idx(c, d);
        have[u].pb({v, IDX});
        have[v].pb({u, IDX});
        if(a == c && b == d) {
            ans[IDX] = inf;
        }
        IDX++;
    }

    DSU dsu(n * m + 1);
    dsu.init();
    vector<int> dx = {1, -1, 0, 0};
    vector<int> dy = {0, 0, 1, -1};
    for(int x = val.size() - 1; ~x; x--) {
        for(auto [i, j] : val[x]) {
            for(int k = 0; k < 4; k++) {
                int ni = i + dx[k];
                int nj = j + dy[k];
                if(ni < 0 || nj < 0 || ni == n || nj == m || a[ni][nj] < a[i][j]) continue;
                int u = idx(i, j);
                int v = idx(ni, nj);
                dsu.unite(u, v, x);
            }
        }
    }

    for(int i = 0; i < q; i++) {
        int x = qr[i][2];
        int y = qr[i][5];
        int z = ans[i];
        if(min(x, y) <= z) {
            cout << abs(x - y) << '\n';
        }
        else {
            cout << x + y - 2 * z << '\n';
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

Submission Info

Judge Result