kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

DSL_2_C: Range Search (kD Tree)

平面上の点の集合の中から、指定された長方形に入っているものを選ぶ問題
っていうと簡単そうだけど点の数が50万、判定が2万回となると一筋縄ではいかない
「高速な入出力方法を使用してください」とか書いてあるし
ていうか思考★★★★、実装★★★★て(腰が引けてる

アルゴリズムについては書いてない
kD Treeというくらいだから木だろう、2万回も判定するんだから
前処理に時間をかけてもいいだろう、くらいは思いついたけど
ヒントの図の、たてよこあみだくじみたいなのはなんだろう
たぶん前処理を図にしたものだと思うんだけど
kD Treeってやつを自分で考えて再現するのは難しいかなあ

とりあえず今日は単純に書いてTLE出す

def read_points():
    n = int(input())
    points = []
    for _ in range(n):
        x, y = [int(x) for x in input().split()]
        points.append((x, y))
    return n, points

def pick_points(sx, tx, sy, ty, n, points):
    for i in range(n):
        if sx <= points[i][0] <= tx and \
           sy <= points[i][1] <= ty:
            print(i)
    print()

def process_queries(n, points):
    q = int(input())
    for _ in range(q):
        sx, tx, sy, ty = [int(x) for x in input().split()]
        pick_points(sx, tx, sy, ty, n, points)

def main():
    n, points = read_points()
    process_queries(n, points)

if __name__ == '__main__':
    main()

#11でTLE
点の数が80000個
問い合わせの数はわからない

そんなにループが入れ子になってるわけじゃなくて
オーダはnqだよな
(log n)qとかあるいはqになるアルゴリズム
もしかしたら問い合わせもひとつずつ処理するんじゃなくて
全部読み込んでいっぺんに調べるみたいなこともあるかもしれない