Submission #17400113

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 inc i
    i += 1
    until @a.size < i
      @a[i-1] += 1
      i += i&-i
    end
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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 inc i
		i += 1
		until @a.size < i
			@a[i-1] += 1
			i += i&-i
		end
	end
end

(N,Q),C,*LR = $<.map{|ln| ln.split.map(&:to_i) }

LR.map!.with_index{|(l,r),q| [r-1,l-1,q] }.sort_by!{|r,| r }

A = [0]*Q     # answer
LOC = [nil]*N # last occurrence of colors
COL = BIT.new N
C.each_with_index{|c,i|
	COL.inc N-1-LOC[-c] if LOC[-c]
	LOC[-c] = i
	while LR[0][0] == i
		_,l,q = LR.shift
		A[q] = i-l+1-COL[N-1-l]
	end rescue break
}
puts A

Submission Info

Judge Result