Submission #25580892

---

Source Code Expand

L,Q=map(int,input().split())
CX=[list(map(int,input().split())) for i in range(Q)]
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
        self.Length=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            self.Length[rm]+=self.Length[rn]
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]
    def length(self,n):
        return self.Length[self.root(n)]
    def components(self):
        return sum(e<0 for e in self.Parent)
d=[]
for c,x in CX:
    if c==1:
        d.append(x)
d.sort()
u=UnionFind(len(d)+1)
d=[0]+d+[L]
for i in range(len(d)-1):
    u.Length[i]=d[i+1]-d[i]
from bisect import bisect_left
a=[]
for c,x in reversed(CX):
    b=bisect_left(d,x)
    if c==1:
        u.unite(b-1,b)
    else:
        a.append(u.length(b-1))
print(*reversed(a),sep='\n')

Submission Info

Judge Result