Submission #65275305

---

Source Code Expand

class BIT
	def initialize n
		@a = [0]*(n+1) # 1-indexed internally
	end

	def [] i
		i += 1
		s = 0
		while 0<i
			s += @a[i]
			i &= i-1
		end
		return s
	end
	def lb s
		z = @a.size-1
		i,t,b = 0,0,1<<z.bit_length
		t += @a[i|=b] if i|b<=z && t+@a[i|b]<s while 0<b >>= 1
		return i # i は１大きい内部インデックス(もしくは 0)だけど、求めた添字が s より小さい値を返す最大の添字であり、s 以上を返す最小の添字としては +1 したものを返したいから、足し引きして内部インデックスそのままの値を返す(アクセス可能な範囲を１超えることがあります。サイズに等しい値)。
	end
 
	def add i,d
		i += 1
		while i<@a.size
			@a[i] += d
			i += i&-i
		end
	end
	def inc i; add i,1 end
	def dec i; add i,-1 end
end

Qry = gets.to_i.times.map{ gets.split }
Xs,Ys = [],[]
Qry.each{|t,s|
	(t==?1 ? Xs : Ys)<<s
}
Xs.sort!.uniq!
Ys.sort!.uniq!
X2I = Xs.each_with_index.to_h
Y2I = Ys.each_with_index.to_h

D = [nil]*X2I.size # X がどの Y を除外するか
Xs.each_with_index{|x,i|
	j = Ys.bsearch_index{|y| x<=y }
	if j && Ys[j].start_with?(x)
		k = (j...Ys.size).bsearch{|k|
			! Ys[k].start_with?(x)
		}||Ys.size
		D[i] = j...k
	end
}

DeletedY = BIT.new Ys.size+1
UndeletedY = BIT.new Ys.size+1
puts Qry.map{|t,s|
	case t
	when ?1
		i = X2I[s]
		if r = D[i]
			DeletedY.inc r.begin
			DeletedY.dec r.end
			v = r.begin==0 ? 1 : UndeletedY[r.begin-1]+1
			while (j = UndeletedY.lb v) and j<r.end
				UndeletedY.dec j
			end
		end
	when ?2
		i = Y2I[s]
		if 0<DeletedY[i]
		else
			UndeletedY.inc i
		end
	end
	UndeletedY[Ys.size]
}

Submission Info

Judge Result