結果
問題 | No.1705 Mode of long array |
ユーザー |
|
提出日時 | 2021-10-08 23:29:59 |
言語 | Kotlin (2.1.0) |
結果 |
AC
|
実行時間 | 999 ms / 3,000 ms |
コード長 | 4,506 bytes |
コンパイル時間 | 19,121 ms |
コンパイル使用メモリ | 462,752 KB |
実行使用メモリ | 96,044 KB |
最終ジャッジ日時 | 2024-07-23 07:39:23 |
合計ジャッジ時間 | 61,150 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
コンパイルメッセージ
Main.kt:6:9: warning: variable 'n' is never used val n = nextLong() ^
ソースコード
import java.io.PrintWriterimport java.util.*import kotlin.math.*fun PrintWriter.solve() {val n = nextLong()val m = nextInt()val a = Array(m) { nextLong() }val b = Array(m) { 0L to 0 }for (i in 0 until m) {b[i] = a[i] to i}val seg = SegTree(b, { x, y -> if (x.first > y.first) x else y }, 0L to 0)val q = nextInt()for (_i in 0 until q) {val t = nextInt()val x = nextInt() - 1val y = nextLong()if (t == 1) {seg[x] = seg[x].first + y to seg[x].second} else if (t == 2) {seg[x] = seg[x].first - y to seg[x].second} else {println(seg.allProd().second + 1)}}}class SegTree<Monoid>(private val n: Int, private val op: (Monoid, Monoid) -> Monoid, private val e: Monoid) {private var d: MutableList<Monoid>private var size = 1private var log = 0init {while (size < n) {size *= 2log++}d = MutableList(2 * size) { e }}constructor(a: Array<Monoid>, op: (Monoid, Monoid) -> Monoid, e: Monoid) : this(a.count(), op, e) {for (i in 0 until n) {d[size + i] = a[i]}for (i in size - 1 downTo 1) update(i)}operator fun set(p: Int, x: Monoid) {if (p !in 0 until n) {throw IllegalArgumentException()}val p1 = p + sized[p1] = xfor (i in 1..log) {update(p1 shr i)}}operator fun get(p: Int): Monoid {if (p !in 0 until n) {throw IllegalArgumentException()}return d[p + size]}fun prod(range: IntRange): Monoid {val l = range.firstval r = range.last + 1if (l !in 0..r || r > n) {throw IllegalArgumentException()}var sml = evar smr = evar l1 = l + sizevar r1 = r + sizewhile (l1 < r1) {if (l1 and 1 != 0) sml = op(sml, d[l1++])if (r1 and 1 != 0) smr = op(d[--r1], smr)l1 /= 2r1 /= 2}return op(sml, smr)}fun allProd(): Monoid {return d[1]}fun maxRight(l: Int, f: (Monoid) -> Boolean): Int {if (l !in 0..n || !f(e)) {throw IllegalArgumentException()}if (l == n) return nvar l1 = l + sizevar sm = edo {while (l1 % 2 == 0) l1 /= 2if (!f(op(sm, d[l1]))) {while (l1 < size) {l1 *= 2if (f(op(sm, d[l1]))) {sm = op(sm, d[l1])l1++}}return l1 - size}sm = op(sm, d[l1])l1++} while ((l1 and -l1) != l1)return n}fun minLeft(r: Int, f: (Monoid) -> Boolean): Int {if (r !in 0..n || !f(e)) {throw IllegalArgumentException()}if (r == 0) return 0var r1 = r + sizevar sm = edo {r1--while (r1 > 1 && r1 % 2 != 0) r1 /= 2if (!f(op(d[r1], sm))) {while (r1 < size) {r1 = 2 * r1 + 1if (f(op(d[r1], sm))) {sm = op(d[r1], sm)r1--}}return r1 + 1 - size}sm = op(d[r1], sm)} while ((r1 and -r1) != r1)return 0}private fun update(k: Int) {d[k] = op(d[2 * k], d[2 * k + 1])}fun joinToString(s: String = ", "): String {return (0 until n).map { this[it] }.joinToString(s)}}fun main() {Thread(null, {val writer = PrintWriter(System.out, false)writer.solve()writer.flush()}, "solve", 1.shl(26)).apply { setUncaughtExceptionHandler { _, e -> e.printStackTrace(); kotlin.system.exitProcess(1) } }.apply { start() }.join()}// region Scannerprivate var st = StringTokenizer("")private val br = System.`in`.bufferedReader()fun next(): String {while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())return st.nextToken()}fun nextInt() = next().toInt()fun nextLong() = next().toLong()fun nextLine() = br.readLine()fun nextDouble() = next().toDouble()// endregion