結果
問題 | No.1920 Territory |
ユーザー |
![]() |
提出日時 | 2022-03-25 10:30:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,148 ms / 5,000 ms |
コード長 | 4,307 bytes |
コンパイル時間 | 257 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 169,332 KB |
最終ジャッジ日時 | 2024-06-28 15:53:04 |
合計ジャッジ時間 | 55,064 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
from sys import stdininput=lambda :stdin.readline()[:-1]class UnionFind():def __init__(self, n):self.n = nself.parents = [-1] * ndef find(self, x):if self.parents[x] < 0:return xelse:self.parents[x] = self.find(self.parents[x])return self.parents[x]def union(self, x, y):x = self.find(x)y = self.find(y)if x == y:returnif self.parents[x] > self.parents[y]:x, y = y, xself.parents[x] += self.parents[y]self.parents[y] = xdef same(self, x, y):return self.find(x) == self.find(y)def roots(self):return [i for i, x in enumerate(self.parents) if x < 0]class SegTree:def __init__(self, init_val, segfunc, ide_ele):n = len(init_val)self.segfunc = segfuncself.ide_ele = ide_eleself.num = 1 << (n - 1).bit_length()self.tree = [ide_ele] * 2 * self.numfor i in range(n):self.tree[self.num + i] = init_val[i]for i in range(self.num - 1, 0, -1):self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])def update(self, k, x):k += self.numself.tree[k] = xwhile k > 1:self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])k >>= 1def query(self, l, r):res = self.ide_elel += self.numr += self.numwhile l < r:if l & 1:res = self.segfunc(res, self.tree[l])l += 1if r & 1:res = self.segfunc(res, self.tree[r - 1])l >>= 1r >>= 1return resclass ordered_set:def __init__(self,size):self.inf=10**9self.size=sizedef segfunc(x,y):return max(x,y)self.seg_max=SegTree([-self.inf]*size,segfunc,-self.inf)def segfunc(x,y):return min(x,y)self.seg_min=SegTree([self.inf]*size,segfunc,self.inf)def add(self,x):self.seg_max.update(x,x)self.seg_min.update(x,x)def remove(self,x):self.seg_max.update(x,-self.inf)self.seg_min.update(x,self.inf)def get_max(self,x):# x より小さい最大元return self.seg_max.query(0,x)def get_min(self,x):# x より大きい最小元return self.seg_min.query(x+1,self.size)n,m=map(int,input().split())query=[]for i in range(n):y,x1,x2=map(int,input().split())query.append((3*x1-1,3,y,0))query.append((3*x2+1,2,y,0))for i in range(m):x,y1,y2=map(int,input().split())query.append((3*x,1,y1,y2))query.sort(key=lambda x:x[0])k=2*10**5+10inf=10**9uf=UnionFind(k)set1=ordered_set(k) # y 座標の集合を管理set2=ordered_set(k) # 区間の左端の集合を管理ans=-n-muse=[0]*(k)itv_right=[-1]*k # 区間の右端を記録for x,t,y1,y2 in query:if t==1:# y 軸に平行な線分の処理if set1.get_max(y2+1)<y1:ans+=1continueL=set2.get_max(y1+1)if L!=-inf and itv_right[L]>=y1:passelse:L=set2.get_min(y1-1)if L>y2:ans+=1continueR=itv_right[L]while R<=y2:l=set2.get_min(R)if l>y2:breakR=itv_right[l]itv_right[l]=-1set2.remove(l)uf.union(L,l)itv_right[L]=Rif t==2:# x 軸に平行な線分の削除set1.remove(y1)L=set2.get_max(y1+1)R=itv_right[L]itv_right[L]=-1r=set1.get_max(y1)l=set1.get_min(y1)if L!=y1:itv_right[L]=relse:set2.remove(y1)if R!=y1:itv_right[l]=Rset2.add(l)if t==3:# x 軸に平行な線分の追加use[y1]=1L=set2.get_max(y1)if L!=-inf:R=itv_right[L]if y1<=R:r=set1.get_max(y1)l=set1.get_min(y1)itv_right[L]=rset2.add(l)itv_right[l]=Ritv_right[y1]=y1set1.add(y1)set2.add(y1)for i in uf.roots():if use[i]==1:ans+=1def segfunc(x,y):return x+yseg=SegTree([0]*k,segfunc,0)for x,t,y1,y2 in query:if t==1:ans+=seg.query(y1,y2+1)if t==2:seg.update(y1,0)if t==3:seg.update(y1,1)print(ans)