Skip to content

Instantly share code, notes, and snippets.

@mumumu
Created February 24, 2020 12:14
Show Gist options
  • Save mumumu/7163e88687895e8489b1cc03693a1a66 to your computer and use it in GitHub Desktop.
Save mumumu/7163e88687895e8489b1cc03693a1a66 to your computer and use it in GitHub Desktop.
import kotlin.math.*
fun main() {
val firstline = readLine()!!.split(" ")
val k = firstline[1].toLong()
val arr = readLine()!!.split(" ").map { it.toLong() }
var pairlist = mutableListOf<Pair<Long, Int>>()
for ((idx, value) in arr.withIndex()) {
pairlist.add(Pair(value, idx))
}
val qmap = mutableMapOf<Int, Int>()
for (i in 0 until k) {
val q = readLine()!!.split(" ").map { it.toInt() }
val fidx = q[0] - 1
val sidx = q[1] - 1
if (arr[fidx] < arr[sidx]) {
if (!qmap.containsKey(sidx)) {
qmap[sidx] = 1
} else {
qmap[sidx] = qmap[sidx]!! + 1
}
}
if (arr[sidx] < arr[fidx]) {
if (!qmap.containsKey(fidx)) {
qmap[fidx] = 1
} else {
qmap[fidx] = qmap[fidx]!! + 1
}
}
}
val slist = pairlist.sortedWith(compareBy({ it.first }, { it.second }))
val lessmap = mutableMapOf<Long, Int>()
var num1 = 0
var prev1 = -1L
for (p in slist) {
if (prev1 == -1L) {
lessmap[p.first] = 0
} else {
if (prev1 != p.first) {
lessmap[p.first] = num1
}
}
prev1 = p.first
num1++
}
var idxmap = mutableMapOf<Int, Int>()
for (p in slist) {
val cur = p.first
val curidx = p.second
var qnum = 0
if (qmap.containsKey(curidx)) {
qnum = qmap[curidx]!!
}
idxmap[curidx] = lessmap[cur]!! - qnum
}
var l = 0
val ans = idxmap.toSortedMap().values
for (v in ans) {
print(v)
if (l == ans.size - 1) {
println("")
} else {
print(" ")
}
l++
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment