結果

問題 No.2786 RMQ on Grid Path
コンテスト
ユーザー tobisatis
提出日時 2024-06-14 22:56:06
言語 C#
(.NET 8.0.404)
結果
MLE  
実行時間 -
コード長 5,536 bytes
コンパイル時間 9,917 ms
コンパイル使用メモリ 168,908 KB
実行使用メモリ 531,108 KB
最終ジャッジ日時 2024-06-14 22:56:35
合計ジャッジ時間 19,872 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 MLE * 1 -- * 24
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (107 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

namespace AtCoder;

#nullable enable

using System.Numerics;

class PersistentArray<T>
{
    const int D = 4;
    const int W = 1 << D;
    const int M = W - 1;
    T Value { get; set; }
    PersistentArray<T>[] Nodes { get; init; }
    PersistentArray(T value, PersistentArray<T>[] nodes) { Value = value; Nodes = nodes; }

    public static PersistentArray<T> Build(T[] array)
    {
        var res = new PersistentArray<T>(array[0], new PersistentArray<T>[W]);
        for (var i = 1; i < array.Length; i++)
        {
            var (j, b) = (i, res);
            while (j > 0)
            {
                var q = j & M;
                if (b.Nodes[q] == null) b.Nodes[q] = new(array[i], new PersistentArray<T>[W]);
                (j, b) = (j >> D, b.Nodes[q]);
            }
            b.Value = array[i];
        }
        return res;
    }

    public T this[long i] => i == 0 ? Value : Nodes[i & M][i >> D];
    public PersistentArray<T> SetItem(int i, T value)
    {
        var nodes = Nodes.AsSpan().ToArray();
        if (i == 0) return new(value, nodes);
        nodes[i & M] = nodes[i & M].SetItem(i >> D, value);
        return new(Value, nodes);
    }
}

readonly struct PersistentUnionFind
{
    PersistentArray<int> Parents { get; init; }

    public PersistentUnionFind(int verticals)
    {
        var a = new int[verticals];
        for (var i = 0; i < verticals; i++) a[i] = -1;
        Parents = PersistentArray<int>.Build(a);
    }
    PersistentUnionFind(PersistentArray<int> parents) { Parents = parents; }

    public (int, int) ParentAndSize(int x)
    {
        var p = Parents[x];
        return p < 0 ? (x, -p) : ParentAndSize(p);
    }
    public int Find(int x) => ParentAndSize(x).Item1;
    public int Size(int x) => ParentAndSize(x).Item2;

    public (int, PersistentUnionFind) Union(int x, int y)
    {
        int sx, sy;
        (x, sx) = ParentAndSize(x);
        (y, sy) = ParentAndSize(y);
        if (sx < sy) (x, y) = (y, x);
        var lp = Parents;
        if (x != y) lp = lp.SetItem(y, x).SetItem(x, -(sx + sy));
        return (x, new(lp));
    }
}

static class Extensions
{
    public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray();
}

class AtCoder
{
    object? Solve()
    {
        var h = Int();
        var w = Int();
        var p = h * w;
        var az = new int[h, w];
        var nz = (p + 1).Repeat(() => new List<(int, int)>());
        for (var i = 0; i < h; i++) for (var j = 0; j < w; j++)
        {
            var n = Int();
            nz[n].Add((i, j));
            az[i, j] = n;
        }
        int C1(int x, int y) => x * w + y;
        var q = Int();
        var queries = new (int, int)[q];
        for (var i = 0; i < q; i++)
        {
            var s = C1(Int() - 1, Int() - 1);
            var t = C1(Int() - 1, Int() - 1);
            queries[i] = (s, t);
        }
        var ufz = new PersistentUnionFind[p + 1];
        ufz[0] = new(p);
        var moves = new[]{ (-1, 0), (0, -1), (0, 1), (1, 0) };
        bool Inside(int x, int y) => 0 <= x && x < h && 0 <= y && y < w;
        for (var i = 1; i <= p; i++)
        {
            var uf = ufz[i - 1];
            foreach (var (x, y) in nz[i]) foreach (var (dx, dy) in moves)
            {
                var nx = x + dx;
                var ny = y + dy;
                if (!Inside(nx, ny)) continue;
                var na = az[nx, ny];
                if (na > i) continue;
                var c0 = C1(x, y);
                var c1 = C1(nx, ny);
                if (uf.Find(c0) == uf.Find(c1)) continue;
                uf = uf.Union(c0, c1).Item2;
            }
            ufz[i] = uf;
        }
        var ans = new int[q];
        for (var i = 0; i < q; i++)
        {
            var (s, t) = queries[i];
            bool F(int x)
            {
                var uf = ufz[x];
                var res = uf.Find(s) == uf.Find(t);
                return res;
            }
            int BinarySearch(int pass, int fail)
            {
                while (Math.Abs(pass - fail) > 1)
                {
                    var middle = (pass + fail) >> 1;
                    if (F(middle)) pass = middle; else fail = middle;
                }
                return pass;
            }
            ans[i] = BinarySearch(p + 1, 0);
        }
        Out(ans);
        return null;
    }

    public static void Main() => new AtCoder().Run();
    public void Run()
    {
        var res = Solve();
        if (res != null)
        {
            if (res is bool yes) res = yes ? "Yes" : "No";
            sw.WriteLine(res);
        }
        sw.Flush();
    }

    string[] input = Array.Empty<string>();
    int iter = 0;
    readonly StreamWriter sw = new(Console.OpenStandardOutput()) { AutoFlush = false };

    string String()
    {
        while (iter >= input.Length) (input, iter) = (Console.ReadLine()!.Split(' '), 0);
        return input[iter++];
    }
    T Input<T>() where T : IParsable<T> => T.Parse(String(), null);
    int Int() => Input<int>();
    void Out(object? x, string? separator = null)
    {
        separator ??= Environment.NewLine;
        if (x is System.Collections.IEnumerable obj and not string)
        {
            var firstLine = true;
            foreach (var item in obj)
            {
                if (!firstLine) sw.Write(separator);
                firstLine = false;
                sw.Write(item);
            }
        }
        else sw.Write(x);
        sw.WriteLine();
    }
}
0