結果

問題 No.1625 三角形の質問
ユーザー chineristACchineristAC
提出日時 2021-05-03 22:16:36
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,174 bytes
コンパイル時間 728 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 593,664 KB
最終ジャッジ日時 2024-07-18 16:10:11
合計ジャッジ時間 10,878 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
56,832 KB
testcase_01 AC 1,540 ms
267,668 KB
testcase_02 MLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

class DemandSegmentTree:
    def __init__(self,n,segfunc,ide_ele):
        self.num = 1<<n
        self.val = {}
        self.e = ide_ele
        self.segfunc = segfunc

    def update(self,k,x):
        k += self.num
        if k not in self.val:
            self.val[k] = self.e
        self.val[k] = self.segfunc(self.val[k],x)
        while k > 1:
            self.val[k>>1] = self.val[k]
            if k^1 in self.val:
                self.val[k>>1] = self.segfunc(self.val[k>>1],self.val[k^1])
            k >>= 1

    def query(self,l,r):
        l += self.num
        r += self.num
        res = self.e
        while l < r:
            if l&1:
                if l in self.val:
                    res = self.segfunc(res,self.val[l])
                l += 1
            if r&1:
                if r-1 in self.val:
                    res = self.segfunc(res,self.val[r-1])
            l >>= 1
            r >>= 1
        return res

class DDSegmentTree:
    def __init__(self,width,n,segfunc,ide_ele):
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (width - 1).bit_length()
        self.tree = [DemandSegmentTree(n,segfunc,ide_ele) for _ in range(2*self.num)]
        self.size = n

    def update(self,l,r,x):
        l += self.num
        while l:
            self.tree[l].update(r,x)
            l >>= 1

    def query(self,a,b,c,d):
        res = self.ide_ele
        a += self.num
        b += self.num
        while a < b:
            if a&1:
                #print(a,self.tree[a].val)
                tmp = self.tree[a].query(c,d)
                res = self.segfunc(res,tmp)
                a += 1
            if b&1:
                #print(b-1,self.tree[b-1].val)
                tmp = self.tree[b-1].query(c,d)
                res = self.segfunc(res,tmp)
            a >>= 1
            b >>= 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())

n,q = mi()
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 i in range(q):
    if query[i][0]==1:
        t,a,b,c,d,e,f = query[i]
        X.add(min(a,c,e))
        X.add(max(a,c,e))
    else:
        t,l,r = query[i]
        X.add(l)
        X.add(r)
X = sorted(X)
comp = {e:i for i,e in enumerate(X)}
N = len(comp)

DDseg = DDSegmentTree(N,20,max,0)
for a,b,c,d,e,f in triangle:
    l,r = min(a,c,e),max(a,c,e)
    l,r = comp[l],comp[r]
    S = area(a,b,c,d,e,f)
    DDseg.update(l,r,S)

for i in range(q):
    if query[i][0]==1:
        t,a,b,c,d,e,f = query[i]
        l,r = min(a,c,e),max(a,c,e)
        l,r = comp[l],comp[r]
        S = area(a,b,c,d,e,f)
        DDseg.update(l,r,S)
    else:
        t,l,r = query[i]
        l,r = comp[l],comp[r]+1

        ans = DDseg.query(l,r,l,r)
        print(ans if ans else -1)
0