Create a gist now

Instantly share code, notes, and snippets.

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=" ")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment