結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from sys import stdin
input=lambda :stdin.readline()[:-1]
class UnionFind():
def __init__(self, n):
self.n = n
self.parents = [-1] * n
def find(self, x):
if self.parents[x] < 0:
return x
else:
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:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
def 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 = segfunc
self.ide_ele = ide_ele
self.num = 1 << (n - 1).bit_length()
self.tree = [ide_ele] * 2 * self.num
for 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.num
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):
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 ordered_set:
def __init__(self,size):
self.inf=10**9
self.size=size
def 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+10
inf=10**9
uf=UnionFind(k)
set1=ordered_set(k) # y
set2=ordered_set(k) #
ans=-n-m
use=[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+=1
continue
L=set2.get_max(y1+1)
if L!=-inf and itv_right[L]>=y1:
pass
else:
L=set2.get_min(y1-1)
if L>y2:
ans+=1
continue
R=itv_right[L]
while R<=y2:
l=set2.get_min(R)
if l>y2:
break
R=itv_right[l]
itv_right[l]=-1
set2.remove(l)
uf.union(L,l)
itv_right[L]=R
if t==2:
# x
set1.remove(y1)
L=set2.get_max(y1+1)
R=itv_right[L]
itv_right[L]=-1
r=set1.get_max(y1)
l=set1.get_min(y1)
if L!=y1:
itv_right[L]=r
else:
set2.remove(y1)
if R!=y1:
itv_right[l]=R
set2.add(l)
if t==3:
# x
use[y1]=1
L=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]=r
set2.add(l)
itv_right[l]=R
itv_right[y1]=y1
set1.add(y1)
set2.add(y1)
for i in uf.roots():
if use[i]==1:
ans+=1
def segfunc(x,y):
return x+y
seg=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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0