結果

問題 No.1625 三角形の質問
ユーザー chineristACchineristAC
提出日時 2021-05-07 20:50:00
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,525 ms / 6,000 ms
コード長 5,596 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 86,768 KB
実行使用メモリ 280,592 KB
最終ジャッジ日時 2023-09-25 20:44:18
合計ジャッジ時間 36,549 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 107 ms
73,776 KB
testcase_01 AC 447 ms
100,184 KB
testcase_02 AC 1,205 ms
185,240 KB
testcase_03 AC 714 ms
161,328 KB
testcase_04 AC 870 ms
154,980 KB
testcase_05 AC 1,282 ms
210,752 KB
testcase_06 AC 2,426 ms
274,452 KB
testcase_07 AC 2,525 ms
275,728 KB
testcase_08 AC 2,474 ms
273,960 KB
testcase_09 AC 2,487 ms
274,360 KB
testcase_10 AC 2,418 ms
275,388 KB
testcase_11 AC 2,431 ms
274,484 KB
testcase_12 AC 2,470 ms
274,416 KB
testcase_13 AC 2,429 ms
274,316 KB
testcase_14 AC 2,398 ms
274,232 KB
testcase_15 AC 2,524 ms
276,276 KB
testcase_16 AC 538 ms
182,348 KB
testcase_17 AC 1,036 ms
258,528 KB
testcase_18 AC 839 ms
197,768 KB
testcase_19 AC 1,196 ms
280,592 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 i in range(n):
    a,b,c,d,e,f = triangle[i]
    l,r = min(a,c,e),max(a,c,e)
    triangle[i] = (l,r,area(a,b,c,d,e,f))
    X.add(l)
    X.add(r)
for i in range(q):
    t,*query = Query[i]
    if t==1:
        a,b,c,d,e,f = query
        l,r = min(a,c,e),max(a,c,e)
        Query[i] = (1,l,r,area(a,b,c,d,e,f))
        X.add(l)
        X.add(r)
    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 l in range(H)]
pre_query = [[] for l in range(H)]
for l,r,S in triangle:
    l = comp[l]
    r = comp[r]
    add_query[l].append((r,S))
for i in range(Q):
    t,*query = Query[i]
    if t==2:
        l,r = query
        l,r = comp[l],comp[r]
        pre_query[l].append((i,r))

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

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:
        l,r,S = query
        idx = comp[l]
        w_list[i].append(r)
        add_query[idx].append((i,r,S))
    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