Instantly share code, notes, and snippets.

# whatalnk/arc080-a.rb Last active Aug 7, 2017

What would you like to do?
AtCoder ARC #080 / ABC #069
 # K-City n, m = gets.chomp.split(" ").map(&:to_i) puts (n - 1) * (m - 1)
 # i18n s = gets.chomp n = s.length puts "#{s[0]}#{n-2}#{s[-1]}"
 # 4-adjacent n = gets.chomp.to_i arr = gets.chomp.split(" ").map(&:to_i) mod4 = Array.new(3, 0) arr.each do |a| cnt = 0 while true break if cnt == 2 if a.even? then cnt += 1 a /= 2 else break end end mod4[cnt] += 1 end x = [mod4[2], mod4[0]].min mod4[0] -= x mod4[2] -= x if mod4[0] > 1 then puts "No" elsif mod4[0] == 1 if mod4[1] == 0 then puts "Yes" else puts "No" end else puts "Yes" end
 # Grid Coloring h, w = gets.chomp.split(" ").map(&:to_i) n = gets.chomp.to_i arr = gets.chomp.split(" ").map(&:to_i) x = [] arr.each_with_index do |a, i| x += Array.new(a, i+1) end i = 1 x.each_slice(w) do |a| if i.even? puts a.reverse.join(" ") else puts a.join(" ") end i += 1 end
 # TLE import heapq MAX_N = 1 << 17 INT_MAX = 2**31 - 1 class SegmentTree(): def __init__(self, n_): self.n = 1 while self.n < n_: self.n *= 2 self.dat = [INT_MAX] * (2 * self.n - 1) def update(self, k, a): k += (self.n - 1) self.dat[k] = a while k > 0: k = (k - 1) // 2 if self.dat[k * 2 + 1] < self.dat[k * 2 + 2]: self.dat[k] = self.dat[k * 2 + 1] else: self.dat[k] = self.dat[k * 2 + 2] # self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2]) def query(self, a, b, k, l, r): if (r <= a) or (b <= l): return INT_MAX if (a <= l) and (r <= b): return self.dat[k] else: vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2) vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r) if vl < vr: return vl else: return vr # return min(vl, vr) def wrap_query(type, a, b, k, l): if type == "even": if a % 2 == 0: ret = st_even.query(a, b, k, l, st_even.n) else: ret = st_odd.query(a, b, k, l, st_odd.n) else: if a % 2 == 0: ret = st_odd.query(a, b, k, l, st_odd.n) else: ret = st_even.query(a, b, k, l, st_even.n) return ret class Item(): def __init__(self, mini, left, right): self.mini = mini self.left = left self.right = right if __name__ == '__main__': n = int(input()) arr = list(map(int, input().split(" "))) st_even = SegmentTree(n) st_odd = SegmentTree(n) h = dict() for i in range(n): h[arr[i]] = i if i % 2 == 0: st_even.update(i, arr[i]) else: st_odd.update(i, arr[i]) q = [None] * n hq = [] x = wrap_query("even", 0, n, 0, 0) heapq.heappush(hq, (x, Item(h[x], 0, n))) ii = 0 while len(hq) != 0: q0, item = heapq.heappop(hq) l = item.left r = item.right i = item.mini q[ii] = q0 ii += 1 # q.append(q0) q1 = wrap_query("odd", i, r, 0, 0) j = h[q1] q[ii] = q1 ii += 1 # q.append(q1) if i - l > 1: x0 = wrap_query("even", l, i, 0, 0) heapq.heappush(hq, (x0, Item(h[x0], l, i))) if j - (i+1) > 1: x1 = wrap_query("even", i+1, j, 0, 0) heapq.heappush(hq, (x1, Item(h[x1], i+1, j))) if r - (j + 1) > 1: x2 = wrap_query("even", j+1, r, 0, 0) heapq.heappush(hq, (x2, Item(h[x2], j+1, r))) print(*q, sep=" ")