結果

問題 No.1625 三角形の質問
ユーザー chineristACchineristAC
提出日時 2021-05-07 20:14:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,397 ms / 6,000 ms
コード長 6,354 bytes
コンパイル時間 1,658 ms
コンパイル使用メモリ 86,688 KB
実行使用メモリ 292,940 KB
最終ジャッジ日時 2023-09-25 20:40:31
合計ジャッジ時間 47,641 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 107 ms
73,748 KB
testcase_01 AC 594 ms
101,024 KB
testcase_02 AC 1,762 ms
189,392 KB
testcase_03 AC 912 ms
163,948 KB
testcase_04 AC 1,261 ms
154,880 KB
testcase_05 AC 1,678 ms
208,876 KB
testcase_06 AC 3,397 ms
291,564 KB
testcase_07 AC 3,382 ms
290,620 KB
testcase_08 AC 3,318 ms
291,892 KB
testcase_09 AC 3,283 ms
290,960 KB
testcase_10 AC 3,313 ms
292,940 KB
testcase_11 AC 3,284 ms
292,288 KB
testcase_12 AC 3,289 ms
291,052 KB
testcase_13 AC 3,223 ms
291,540 KB
testcase_14 AC 3,356 ms
290,480 KB
testcase_15 AC 3,312 ms
290,628 KB
testcase_16 AC 547 ms
175,272 KB
testcase_17 AC 1,386 ms
263,860 KB
testcase_18 AC 851 ms
192,036 KB
testcase_19 AC 1,497 ms
285,404 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def merge_sort(A,B):
    pos_A,pos_B = 0,0
    n,m = len(A),len(B)
    res = []
    while pos_A < n and pos_B < m:
        a,b = A[pos_A],B[pos_B]
        if a < b:
            res.append(a)
            pos_A += 1
        else:
            res.append(b)
            pos_B += 1
    res += A[pos_A:]
    res += B[pos_B:]
    return res

class SegmentTree:
    def __init__(self, n, segfunc, ide_ele):
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        #self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * n
        self.size = n

    def update(self, k, x):
        k += self.size
        if self.tree[k] > x:
            return
        self.tree[k] = self.segfunc(self.tree[k],x)
        while k > 1:
            if self.tree[k >> 1] > x:
                return
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        if r==self.size:
            r = self.size

        res = self.ide_ele

        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

class BIT():
    def __init__(self,n):
        self.BIT=[-1]*(n+1)
        self.num=n

    def query(self,idx):
        res = -1
        while idx > 0:
            res = max(res,self.BIT[idx])
            idx -= idx&(-idx)
        return res

    #Ai += x O(logN)
    def update(self,idx,x):
        idx += 1
        while idx <= self.num:
            self.BIT[idx] = max(self.BIT[idx],x)
            idx += idx&(-idx)
        return

class SegmenTree2D:
    def __init__(self,n,w_list,segfunc,ide_ele):
        self.num = n
        self.segfunc = segfunc
        self.ide_ele = ide_ele

        self.val = [[] for i in range(2 * n)]
        self.segtree = [None for i in range(2 * n)]
        for i in range(n):
            self.val[i+self.num] = w_list[i]
            if self.val[i+self.num]:
                self.segtree[i+self.num] = BIT(len(self.val[i+self.num]))
        for i in range(self.num-1,0,-1):
            self.val[i] = merge_sort(self.val[2*i],self.val[2*i+1])
            if self.val[i]:
                self.segtree[i] = BIT(len(self.val[i]))

    def update(self,l,r,x):
        l += self.num
        while l:
            #assert self.segment[l]
            idx = bisect.bisect_left(self.val[l],r)
            self.segtree[l].update(idx,x)
            l >>= 1

    def query(self,t,r):
        lx = 0
        rx = t+1
        ly = 0
        ry = r+1

        res = self.ide_ele
        lx += self.num
        rx += self.num
        while lx < rx:
            if lx&1:
                if self.val[lx]:
                    tmp_r = bisect.bisect_left(self.val[lx],ry)
                    res = self.segfunc(res,self.segtree[lx].query(tmp_r))
                lx += 1
            if rx&1:
                if self.val[rx-1]:
                    tmp_r = bisect.bisect_left(self.val[rx-1],ry)
                    res = self.segfunc(res,self.segtree[rx-1].query(tmp_r))

            lx >>= 1
            rx >>= 1

        return res

def area(a,b,c,d,e,f):
    A,B,C,D = c-a,d-b,e-a,f-b
    return abs(A*D-B*C)

import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import gcd,log

input = lambda :sys.stdin.buffer.readline()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

def test(N,Q):
    triangle = []
    for i in range(N):
        S = 0
        while not S:
            t = [random.randint(1,10**9) for i in range(6)]
            a,b,c,d,e,f = t
            S = area(a,b,c,d,e,f)
        triangle.append((a,b,c,d,e,f))
    query = []
    for i in range(Q):
        if i&1:
            t = 2
            l = random.randint(1,10**5)
            r = random.randint(l+1,10**9)
            query.append((t,l,r))
        else:
            t = 1
            q = 1
            S = 0
            while not S:
                t = [random.randint(1,10**9) for i in range(6)]
                a,b,c,d,e,f = t
                S = area(a,b,c,d,e,f)
            query.append((q,a,b,c,d,e,f))
    return triangle,query

def area(a,b,c,d,e,f):
    A,B,C,D = c-a,d-b,e-a,f-b
    return abs(A*D-B*C)

import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import gcd,log

input = lambda :sys.stdin.buffer.readline()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

n,q = mi()
Q = q
triangle = [tuple(mi()) for i in range(n)]
Query = [tuple(mi()) for i in range(q)]

X = set()
for a,b,c,d,e,f in triangle:
    X.add(min(a,c,e))
    X.add(max(a,c,e))
for t,*query in Query:
    if t==1:
        a,b,c,d,e,f = query
        X.add(min(a,c,e))
        X.add(max(a,c,e))
    else:
        l,r = query
        X.add(l)
        X.add(r)
X = sorted(X)
comp = {e:i for i,e in enumerate(X)}
H = len(comp)

ans = [-1 for i in range(Q)]
add_query = [[] for r in range(H)]
pre_query = [[] for r in range(H)]
for a,b,c,d,e,f in triangle:
    l = comp[min(a,c,e)]
    r = comp[max(a,c,e)]
    add_query[r].append((l,area(a,b,c,d,e,f)))
for i in range(Q):
    t,*query = Query[i]
    if t==2:
        l,r = query
        l,r = comp[l],comp[r]
        pre_query[r].append((i,l))

Seg = SegmentTree(H,max,-1)
for r in range(H):
    for l,S in add_query[r]:
        Seg.update(l,S)
    for idx,l in pre_query[r]:
        ans[idx] = max(ans[idx],Seg.query(l,H))

w_list = [[] for i in range(Q)]
add_query = [[] for i in range(H)]
pre_query = [[] for r in range(H)]
for i in range(Q):
    t,*query = Query[i]
    if t==1:
        a,b,c,d,e,f = query
        idx = comp[min(a,c,e)]
        w_list[i].append(max(a,c,e))
        add_query[idx].append((i,max(a,c,e),area(a,b,c,d,e,f)))
    else:
        l,r = query
        l = comp[l]
        pre_query[l].append((i,r))

seg = SegmenTree2D(Q,w_list,max,-1)
for l in range(H-1,-1,-1):
    for t,r,S in add_query[l]:
        seg.update(t,r,S)
    for t,r in pre_query[l]:
        ans[t] = max(ans[t],seg.query(t,r))
        

for i in range(Q):
    if Query[i][0]==2:
        print(ans[i])
0