結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー |
![]() |
提出日時 | 2021-07-23 10:46:56 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 1,044 ms / 3,000 ms |
コード長 | 6,073 bytes |
コンパイル時間 | 15,226 ms |
コンパイル使用メモリ | 295,400 KB |
実行使用メモリ | 19,584 KB |
最終ジャッジ日時 | 2024-07-18 07:14:06 |
合計ジャッジ時間 | 25,467 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 13 |
ソースコード
# require "/scanner"# ### Specifications## ```plain# Inside input macro | Expanded code# ----------------------------------------------+---------------------------------------# Uppercase string: Int32, Int64, Float64, etc. | {}.new(Scanner.s)# s | Scanner.s# c | Scanner.c# Other lowercase string: i, i64, f, etc. | Scanner.s.to_{}# operator[]: type[size] | Array.new(input(size)) { input(type) }# Tuple literal: {t1, t2, t3} | {input(t1), input(t2), input(t3)}# Array literal: [t1, t2, t3] | [input(t1), input(t2), input(t3)]# Range literal: t1..t2 | input(t1)..input(t2)# If: cond ? t1 : t2 | cond ? input(t1) : input(t2)# Assign: target = value | target = input(value)# ```## ### Examples## Input:# ```plain# 5 3# foo bar# 1 2 3 4 5# ```# ```# n, m = input(Int32, Int64) # => {5, 10i64}# input(String, Char[m]) # => {"foo", ['b', 'a', 'r']}# input(Int32[n]) # => [1, 2, 3, 4, 5]# ```# ```# n, m = input(i, i64) # => {5, 10i64}# input(s, c[m]) # => {"foo", ['b', 'a', 'r']}# input(i[n]) # => [1, 2, 3, 4, 5]# ```## Input:# ```plain# 2 3# 1 2 3# 4 5 6# ```## ```# h, w = input(i, i) # => {2, 3}# input(i[h, w]) # => [[1, 2, 3], [4, 5, 6]]# ```# ```# input(i[i][i]) # => [[1, 2, 3], [4, 5, 6]]# ```## Input:# ```plain# 5 3# 3 1 4 2 5# 1 2# 2 3# 3 1# ```# ```# n, m = input(i, i) # => {5, 3}# input(i.pred[n]) # => [2, 0, 3, 1, 4]# input({i - 1, i - 1}[m]) # => [{0, 1}, {1, 2}, {2, 0}]# ```## Input:# ```plain# 3# 1 2# 2 2# 3 2# ```# ```# input({tmp = i, tmp == 1 ? i : i.pred}[i]) # => [{1, 2}, {2, 1}, {3, 1}]# ```class Scannerprivate def self.skip_to_not_spacepeek = STDIN.peeknot_space = peek.index { |x| x != 32 && x != 10 } || peek.sizeSTDIN.skip(not_space)enddef self.cskip_to_not_spaceSTDIN.read_char.not_nil!enddef self.sskip_to_not_spacepeek = STDIN.peekif index = peek.index { |x| x == 32 || x == 10 }STDIN.skip(index + 1)return String.new(peek[0, index])endString.build do |buffer|loop dobuffer.write peekSTDIN.skip(peek.size)peek = STDIN.peekbreak if peek.empty?if index = peek.index { |x| x == 32 || x == 10 }buffer.write peek[0, index]STDIN.skip(index)breakendendendendendmacro internal_input(s, else_ast){% if Scanner.class.has_method?(s.id) %}Scanner.{{s.id}}{% elsif s.stringify == "String" %}Scanner.s{% elsif s.stringify == "Char" %}Scanner.c{% elsif s.stringify =~ /[A-Z][a-z0-9_]*/ %}{{s.id}}.new(Scanner.s){% elsif String.has_method?("to_#{s}".id) %}Scanner.s.to_{{s.id}}{% else %}{{else_ast}}{% end %}endmacro internal_input_array(s, args){% for i in 0...args.size %}%size{i} = input({{args[i]}}){% end %}{% begin %}{% for i in 0...args.size %} Array.new(%size{i}) { {% end %}input({{s.id}}){% for i in 0...args.size %} } {% end %}{% end %}endmacro input(s){% if s.is_a?(Call) %}{% if s.receiver.is_a?(Nop) %}internal_input({{s.name}}, {{s.name}}({% for argument in s.args %} input({{argument}}), {% end %})){% elsif s.name.stringify == "[]" %}internal_input_array({{s.receiver}}, {{s.args}}){% else %}input({{s.receiver}}).{{s.name.id}}({% for argument in s.args %} input({{argument}}), {% end %}) {{s.block}}{% end %}{% elsif s.is_a?(TupleLiteral) %}{ {% for i in 0...s.size %} input({{s[i]}}), {% end %} }{% elsif s.is_a?(ArrayLiteral) %}[ {% for i in 0...s.size %} input({{s[i]}}), {% end %} ]{% elsif s.is_a?(RangeLiteral) %}Range.new(input({{s.begin}}), input({{s.end}}), {{s.excludes_end?}}){% elsif s.is_a?(If) %}{{s.cond}} ? input({{s.then}}) : input({{s.else}}){% elsif s.is_a?(Assign) %}{{s.target}} = input({{s.value}}){% else %}internal_input({{s.id}}, {{s.id}}){% end %}endmacro input(*s){ {% for s in s %} input({{s}}), {% end %} }end# require "/datastructure/binary_indexed_tree"class BinaryIndexedTree(T)getter size : Int32def initialize(@size)@a = Array(T).new(@size + 1, T.zero)enddef initialize(a : Array(T))@a = [T.zero]@a.concat a@size = a.size(1...size).each do |i|j = i + (i & -i)next if j > size@a[j] += @a[i]endend# Add *x* to `a[i]`.def add(i : Int, x) : Nilraise IndexError.new unless 0 <= i < sizei += 1while i <= size@a[i] += xi += i & -iendend# Set *x* to `a[i]`.def set(i : Int, x) : Niladd(i, x - self[i, 1])end# Culculates sum of `a[0...i]`.def left_sum(i : Int) : Traise IndexError.new unless 0 <= i <= sizesum = T.zerowhile i > 0sum += @a[i]i -= i & -iendsumenddef [](start : Int, count : Int) : Tleft_sum(start + count) - left_sum(start)enddef [](range : Range) : Tself[*Indexable.range_to_index_and_count(range, size) || raise IndexError.new]enddef to_a : Array(T)(0...size).map { |i| self[i..i] }endend# require "/array/compress"class Array(T)def compress(values : Array(T), *, index : Int = 0)map do |x|index + values.bsearch_index { |y| y >= x }.not_nil!endenddef compress(*, index : Int = 0) : Array(Int32)compress(uniq.sort!, index: index)endendn = input(i)a = input(i[n]).compressbit = BinaryIndexedTree(Int64).new(n)ans = 0i64n.times do |i|bit.add(a[i], 1)ans += bit[a[i] + 1..]endputs ans(0...n - 1).each do |i|ans -= bit[0...a[i]]bit.add(a[i], -1)bit.add(a[i], 1)ans += bit[a[i] + 1..]puts ansend