結果

問題 No.1625 三角形の質問
コンテスト
ユーザー chineristAC
提出日時 2021-05-07 01:48:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 4,734 ms / 6,000 ms
コード長 4,744 bytes
コンパイル時間 245 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 318,048 KB
最終ジャッジ日時 2024-07-18 16:32:56
合計ジャッジ時間 58,953 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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
        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.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 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] = 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()
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(H)]
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 i in range(Q):
    t,*query = Query[i]
    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]
        res = max(ans[i],seg.query(l_idx,r_idx+1,l,r+1))
        print(res)
0