AtCoder Beginner Contest 436 C

https://atcoder.jp/contests/abc436/tasks/abc436_c

各ブロックの左上を記録しておきます。範囲が広いので配列は使えないので連想配列的なものを使えばよいのでPythonで書くのは簡単ですが、Rではそう簡単にはいきません。
まず、hashというライブラリを使えば簡単ですが、

> library(hash)
hash-2.2.6.3 provided by Decision Patterns

> m <- hash()
> s <- sprintf("%d,%d", 1, 1)
> m[[s]] <- TRUE
> has.key(s, m)
 1,1
TRUE
> m[[s]]
[1] TRUE

しかし、AtCoderでは基本的にライブラリを使えません。
R内の環境変数があるのですが、

> m <- new.env(hash=TRUE, parent=emptyenv())
> m[[s]] <- TRUE
> is.null(m[[s]])
[1] FALSE
> m[[s]]
[1] TRUE

これはとても遅くて間に合いません。
自力で二分探索に持ち込むことにします。
まず、M回の操作で置く予定の場所を集めます。これをソートしておきます。あと値をFALSEにしておきます。そうして、そこにブロックの座標とその隣の座標が全てキーが無いかあってもFALSEになっていれば置けます。
しかし、これでも全然間に合わないようです。

# (r, c)は(R, C)より辞書順で小さいか
is.less <- function(r, c, R, C) {
    if(r == R) {
        return(c < C)
    }
    else {
        return(r < R)
    }
}

binary.search <- function(first, last, r, c, df) {
    mid <- (first + last) %/% 2
    R <- df$R[mid+1]
    C <- df$C[mid+1]
    if(df$R[first+1] == r && df$C[first+1] == c) {
        return(first+1)
    }
    else if(last - first == 1) {
        return(-1)
    }
    else if(is.less(r, c, R, C)) {
        return(binary.search(first, mid, r, c, df))
    }
    else {
        return(binary.search(mid, last, r, c, df))
    }
}

# ブロックを置けるなら、ブロックが何番目のレコードかを返す
# 置けないのなら-1を返す
find.match.row <- function(R, C, df)  {
    row0 <- 1
    for(i in -1:1) {
        for(j in -1:1) {
            r <- R + i
            c <- C + j
            row <- binary.search(0, nrow(df), r, c, df)
            if(row == -1) {
                next
            }
            else if(df$exists[row]) {
                return(-1)
            }
            else if(r == R && c == C) {
                row0 <- row
            }
        }
    }
    return(row0)
}

v <- scan("stdin", integer())

N <- v[1]
M <- v[2]

# データフレームを作る
R <- integer(M)
C <- integer(M)
exists <- logical(M)
for(i in 1:M) {
    R[i] <- v[i*2+1]
    C[i] <- v[i*2+2]
}
orig_df <- data.frame(R, C, exists)
ordered_df <- orig_df[order(orig_df$R, orig_df$C), ]
same <- ordered_df$R[-1] == ordered_df$R[-nrow(ordered_df)] &
        ordered_df$C[-1] == ordered_df$C[-nrow(ordered_df)]
# グループ番号を作成
grp <- cumsum(c(TRUE, !same))
# 重複を取り除く
df <- ordered_df[!duplicated(grp), ]

counter <- 0
for(i in 1:M) {
    r <- find.match.row(R[i], C[i], df)
    if(r != -1) {
        df$exists[r] <- TRUE
        counter <- counter + 1
    }
}
cat(counter, "\n")