結果

問題 No.1625 三角形の質問
ユーザー chineristACchineristAC
提出日時 2021-05-04 02:47:38
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,329 bytes
コンパイル時間 245 ms
コンパイル使用メモリ 82,164 KB
実行使用メモリ 357,544 KB
最終ジャッジ日時 2024-07-18 16:15:22
合計ジャッジ時間 81,087 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
57,196 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 TLE -
testcase_14 WA -
testcase_15 TLE -
testcase_16 AC 831 ms
204,212 KB
testcase_17 AC 1,822 ms
320,200 KB
testcase_18 AC 1,157 ms
217,156 KB
testcase_19 AC 2,189 ms
357,280 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 * self.num
        self.size = n

    def update(self, k, x):
        k += self.num
        self.tree[k] = self.segfunc(self.tree[k],x)
        while k > 1:
            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.num

        res = self.ide_ele

        l += self.num
        r += self.num
        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 SegmenTree2D:
    def __init__(self,n,w_list,segfunc,ide_ele):
        self.num = 1<<(n-1).bit_length()
        self.segfunc = segfunc
        self.ide_ele = ide_ele

        self.val = [[] for i in range(2 * self.num)]
        self.segtree = [None for i in range(2 * self.num)]
        for i in range(n):
            self.val[i+self.num] = w_list[i]
            if self.val[i+self.num]:
                self.segtree[i+self.num] = SegmentTree(len(self.val[i+self.num]),segfunc,ide_ele)
        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] = SegmentTree(len(self.val[i]),segfunc,ide_ele)

    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,lx,rx,ly,ry):
        res = self.ide_ele
        lx += self.num
        rx += self.num
        while lx < rx:
            if lx&1:
                if self.val[lx]:
                    tmp_l = bisect.bisect_left(self.val[lx],ly)
                    tmp_r = bisect.bisect_left(self.val[lx],ry)
                    res = self.segfunc(res,self.segtree[lx].query(tmp_l,tmp_r))
                    lx += 1
            if rx&1:
                if self.val[rx-1]:
                    tmp_l = bisect.bisect_left(self.val[rx-1],ly)
                    tmp_r = bisect.bisect_left(self.val[rx-1],ry)
                    res = self.segfunc(res,self.segtree[rx-1].query(tmp_l,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())

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))
for t,*query in Query:
    if t==1:
        a,b,c,d,e,f = query
        X.add(min(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)

w_list = [[] for i in range(H)]
for a,b,c,d,e,f in triangle:
    idx = comp[min(a,c,e)]
    w_list[idx].append(max(a,c,e))
for t,*query in Query:
    if t==1:
        a,b,c,d,e,f = query
        idx = comp[min(a,c,e)]
        w_list[idx].append(max(a,c,e))
for i in range(H):
    w_list[i].sort()

seg = SegmenTree2D(H,w_list,max,-1)
for a,b,c,d,e,f in triangle:
    idx = comp[min(a,c,e)]
    seg.update(idx,max(a,c,e),area(a,b,c,d,e,f))
for t,*query in Query:
    if t==1:
        a,b,c,d,e,f = query
        idx = comp[min(a,c,e)]
        seg.update(idx,max(a,c,e),area(a,b,c,d,e,f))
    else:
        l,r = query
        l_idx = comp[l]
        r_idx = comp[r]
        print(seg.query(l_idx,r_idx+1,l,r+1))
0