Submission #16923745

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class BIT
  def initialize n
    @a = [0]*n
  end
  def [] i
    i += 1
    s = 0
    while 0 < i
      s += @a[i-1]
      i -= i&-i
    end
    return s
  end
  def []= i,n
    d = n-self[i]
    return unless 0 < d # allow increasing update only
    i += 1
    until @a.size < i
      @a[i-1] += d
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

class BIT
	def initialize n
		@a = [0]*n
	end

	def [] i
		i += 1
		s = 0
		while 0 < i
			s += @a[i-1]
			i -= i&-i
		end
		return s
	end

	def []= i,n
		d = n-self[i]
		return unless 0 < d # allow increasing update only
		i += 1
		until @a.size < i
			@a[i-1] += d
			i += i&-i
		end
	end
end

N,Q = gets.split.map(&:to_i)
bk = (N-2)**2
bb = BIT.new(N-1),BIT.new(N-1)
Q.times{
	b,x = gets.split.map(&:to_i).then{|b,x| [b-1,N-x] }
	y = bb[1-b][x]
	bk -= N-2-y
	bb[b][y] = x
}
p bk

Submission Info

Judge Result