結果

問題 No.2786 RMQ on Grid Path
ユーザー kemuniku
提出日時 2025-02-22 22:56:37
言語 Nim
(2.2.0)
結果
AC  
実行時間 735 ms / 6,000 ms
コード長 8,046 bytes
コンパイル時間 5,269 ms
コンパイル使用メモリ 77,872 KB
実行使用メモリ 89,868 KB
最終ジャッジ日時 2025-02-22 22:57:04
合計ジャッジ時間 23,124 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
import macros
ImportExpand "cplib/tmpl/sheep.nim" <=== "when not declared CPLIB_TMPL_SHEEP:\n    const CPLIB_TMPL_SHEEP* = 1\n    {.warning[UnusedImport]: off.}\n    {.hint[XDeclaredButNotUsed]: off.}\n    import algorithm\n    import sequtils\n    import tables\n    import macros\n    import math\n    import sets\n    import strutils\n    import strformat\n    import sugar\n    import heapqueue\n    import streams\n    import deques\n    import bitops\n    import std/lenientops\n    import options\n    #入力系\n    proc scanf(formatstr: cstring){.header: \"<stdio.h>\", varargs.}\n    proc getchar(): char {.importc: \"getchar_unlocked\", header: \"<stdio.h>\", discardable.}\n    proc ii(): int {.inline.} = scanf(\"%lld\\n\", addr result)\n    proc lii(N: int): seq[int] {.inline.} = newSeqWith(N, ii())\n    proc si(): string {.inline.} =\n        result = \"\"\n        var c: char\n        while true:\n            c = getchar()\n            if c == ' ' or c == '\\n' or c == '\\255':\n                break\n            result &= c\n    #chmin,chmax\n    template `max=`(x, y) = x = max(x, y)\n    template `min=`(x, y) = x = min(x, y)\n    #bit演算\n    proc `%`*(x: int, y: int): int =\n        result = x mod y\n        if y > 0 and result < 0: result += y\n        if y < 0 and result > 0: result += y\n    proc `//`*(x: int, y: int): int{.inline.} =\n        result = x div y\n        if y > 0 and result * y > x: result -= 1\n        if y < 0 and result * y < x: result -= 1\n    proc `%=`(x: var int, y: int): void = x = x%y\n    proc `//=`(x: var int, y: int): void = x = x//y\n    proc `**`(x: int, y: int): int = x^y\n    proc `**=`(x: var int, y: int): void = x = x^y\n    proc `^`(x: int, y: int): int = x xor y\n    proc `|`(x: int, y: int): int = x or y\n    proc `&`(x: int, y: int): int = x and y\n    proc `>>`(x: int, y: int): int = x shr y\n    proc `<<`(x: int, y: int): int = x shl y\n    proc `~`(x: int): int = not x\n    proc `^=`(x: var int, y: int): void = x = x ^ y\n    proc `&=`(x: var int, y: int): void = x = x & y\n    proc `|=`(x: var int, y: int): void = x = x | y\n    proc `>>=`(x: var int, y: int): void = x = x >> y\n    proc `<<=`(x: var int, y: int): void = x = x << y\n    proc `[]`(x: int, n: int): bool = (x and (1 shl n)) != 0\n    #便利な変換\n    proc `!`(x: char, a = '0'): int = int(x)-int(a)\n    #定数\n    #[ include cplib/utils/constants ]#\n    when not declared CPLIB_UTILS_CONSTANTS:\n        const CPLIB_UTILS_CONSTANTS* = 1\n        const INF32*: int32 = 1001000027.int32\n        const INF64*: int = int(3300300300300300491)\n    const INF = INF64\n    #converter\n\n    #range\n    iterator range(start: int, ends: int, step: int): int =\n        var i = start\n        if step < 0:\n            while i > ends:\n                yield i\n                i += step\n        elif step > 0:\n            while i < ends:\n                yield i\n                i += step\n    iterator range(ends: int): int = (for i in 0..<ends: yield i)\n    iterator range(start: int, ends: int): int = (for i in\n            start..<ends: yield i)\n\n    #joinが非stringでめちゃくちゃ遅いやつのパッチ\n    proc join*[T: not string](a: openArray[T], sep: string = \"\"): string = a.mapit($it).join(sep)\n\n    proc dump[T](arr:seq[seq[T]])=\n        for i in 0..<len(arr):\n            echo arr[i]\n"
ImportExpand "cplib/collections/ppunionfind.nim" <=== "when not declared CPLIB_COLLECTIONS_PARTIALPERSISTENTUNIONFIND:\n    const CPLIB_COLLECTIONS_PARTIALPERSISTENTUNIONFIND* = 1\n    import sequtils\n    import algorithm\n    type PartialPersistentUnionFind* = object\n        par_or_siz : seq[int] #0以上のとき、親の頂点番号を表す。0未満のとき、-(集合のサイズ)を表す。\n        time : seq[int] # 親との辺がつながった時間を表す。-1のとき、rootである。\n        size_time : seq[seq[int]]\n        size_value : seq[seq[int]] # ある時点での頂点xがrootとなる集合の大きさ\n        last : int \n\n    proc initPartialPersistentUnionFind*(N:int): PartialPersistentUnionFind=\n        result.par_or_siz = newSeqWith(N,-1)\n        result.time = newseqwith(N,-1)\n        result.size_time = newseqwith(N,@[-1])\n        result.size_value = newseqwith(N,@[1])\n        result.last = -1\n\n    proc root*(self:var PartialPersistentUnionFind,x:int,t:int):int=\n        var now = x\n        while self.time[now] != -1 and self.time[now] <= t:\n            now = self.par_or_siz[now]\n        return now\n\n    proc root*(self:var PartialPersistentUnionFind,x:int):int=\n        return self.root(x,self.last)\n\n    proc unite*(self:var PartialPersistentUnionFind,u,v,t:int):bool {.discardable.}=\n        assert self.last <= t\n        self.last = t\n        var u = self.root(u)\n        var v = self.root(v)\n        if u == v:\n            return false\n        if self.par_or_siz[u] > self.par_or_siz[v]:\n            swap(u,v)\n        self.par_or_siz[u] += self.par_or_siz[v]\n        self.par_or_siz[v] = u\n        self.size_time[u].add(t)\n        self.size_value[u].add(-self.par_or_siz[u])\n        self.time[v] = t\n        return true\n\n    proc unite*(self:var PartialPersistentUnionFind,u,v:int):int {.discardable.}=\n        self.unite(u,v,self.last+1)\n        return self.last\n\n    proc issame*(self:var PartialPersistentUnionFind,u,v,t:int):bool=\n        return self.root(u,t) == self.root(v,t)\n\n    proc issame*(self:var PartialPersistentUnionFind,u,v:int):bool=\n        return self.root(u) == self.root(v)\n\n    proc size*(self:var PartialPersistentUnionFind,x,t:int):int=\n        assert t >= -1\n        var x = self.root(x,t)\n        return self.size_value[x][self.size_time[x].upperBound(t)-1]\n\n    proc size*(self:var PartialPersistentUnionFind,x:int):int=\n        return self.size(x,self.last)\n\n    proc when_unite*(self:var PartialPersistentUnionFind,u,v:int):int=\n        ## 頂点uとvが連結になった時間を返す。\n        ## 連結ではない場合、-2が返る(最悪か？ 時刻-1を開始にしてしまったため仕方なく...)\n        \n        var tu : seq[int]\n        var u = u\n        var tv : seq[int]\n        var v = v\n        while self.time[u] != -1:\n            tu.add(self.time[u])\n            u = self.par_or_siz[u]\n        while self.time[v] != -1:\n            tv.add(self.time[v])\n            v = self.par_or_siz[v]\n        if u != v:\n            return -2\n        while len(tu) > 0 and len(tv) > 0 and tu[^1] == tv[^1]:\n            discard tu.pop()\n            discard tv.pop()\n        result = -1\n        for t in tu:\n            if t > result:\n                result = t\n        for t in tv:\n            if t > result:\n                result = t\n\n    proc size_ge(self:var PartialPersistentUnionFind,x,size:int):int=\n        ## xが属する集合のサイズがsizeを超える時間を返す\n        if size <= 1:\n            return -1\n        var now = x\n        while self.time[now] != -1:\n            now = self.par_or_siz[now]\n            if self.size_value[now][^1] >= size:\n                return self.size_time[now][self.size_value[now].lowerBound(size)]\n\n\n\n\n"


var H,W = ii()

var F = newseqwith(H,lii(W))

var uf = initPartialPersistentUnionFind(H*W)

var tmp : seq[(int,int,int)]

for i in range(H):
    for j in range(W):
        tmp.add((F[i][j],i,j))

tmp.sort()
let GETA = 10**18

var time : seq[(int,int)]

for (x,i,j) in tmp:
    for (di,dj) in [(-1,0),(1,0),(0,-1),(0,1)]:
        let ni = i+di
        let nj = j+dj
        if ni < 0 or ni >= H or nj < 0 or nj >= W:
            continue
        if F[ni][nj] <= F[i][j]:
            var tmp = uf.unite(i*W+j,ni*W+nj)
            time.add((i,j))

var Q = ii()
for i in range(Q):
    var A,B,C,D= ii()
    A-=1;B-=1;C-=1;D-=1
    var idx = uf.when_unite(A*W+B,C*W+D)
    var tmp = F[time[idx][0]][time[idx][1]]
    echo tmp
    #echo ans
0