結果

問題 No.1625 三角形の質問
ユーザー chineristACchineristAC
提出日時 2021-05-07 20:30:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,655 ms / 6,000 ms
コード長 5,869 bytes
コンパイル時間 303 ms
コンパイル使用メモリ 87,192 KB
実行使用メモリ 281,960 KB
最終ジャッジ日時 2023-09-25 20:45:02
合計ジャッジ時間 37,040 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 110 ms
73,792 KB
testcase_01 AC 506 ms
100,092 KB
testcase_02 AC 1,286 ms
180,724 KB
testcase_03 AC 792 ms
164,404 KB
testcase_04 AC 927 ms
149,656 KB
testcase_05 AC 1,279 ms
203,788 KB
testcase_06 AC 2,648 ms
281,288 KB
testcase_07 AC 2,642 ms
281,312 KB
testcase_08 AC 2,655 ms
281,232 KB
testcase_09 AC 2,541 ms
281,276 KB
testcase_10 AC 2,525 ms
280,536 KB
testcase_11 AC 2,449 ms
281,620 KB
testcase_12 AC 2,627 ms
281,436 KB
testcase_13 AC 2,443 ms
281,232 KB
testcase_14 AC 2,483 ms
281,960 KB
testcase_15 AC 2,439 ms
281,392 KB
testcase_16 AC 515 ms
175,396 KB
testcase_17 AC 980 ms
240,672 KB
testcase_18 AC 784 ms
190,160 KB
testcase_19 AC 1,057 ms
261,144 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):
        idx += 1
        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 BIT2D():
    def __init__(self,n,w_list):
        self.num = n

        self.val = [[] for i in range(n+1)]
        self.bit = [None for i in range(n+1)]
        for i in range(1,n+1):
            self.val[i] += w_list[i-1]
            self.val[i] = sorted(set(self.val[i]))
            if self.val[i]:
                self.bit[i] = BIT(len(self.val[i]))

            up_idx = i + (i&(-i))
            if up_idx <= self.num:
                self.val[up_idx] += self.val[i]

    def query(self,t,r):
        res = -1
        t += 1
        idx = t
        while idx:
            if self.val[idx]:
                r_idx = bisect.bisect_right(self.val[idx],r)-1
                res = max(res,self.bit[idx].query(r_idx))
            idx -= idx&(-idx)
        return res

    def update(self,t,r,S):
        t += 1
        while t <= self.num:
            if self.val[t]:
                r_idx = bisect.bisect_right(self.val[t],r)-1
                self.bit[t].update(r_idx,S)
            t += t&(-t)

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,Query = test(n,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 = BIT2D(Q,w_list)
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