| 1 |
import java.io.File import java.io.PrintWriter import java.util.* fun main(args: Array<String>) { val sc = Scanner(File("input.txt")) val pw = PrintWriter("output.txt") val n = sc.nextInt() val heap = Heap(n * 2) repeat(n) { heap.add(sc.nextLong()) } val m = sc.nextInt() repeat(m) { val i = sc.nextInt() pw.println(heap.set(i, heap.get(i) + sc.nextLong())) } pw.println(heap) pw.close() } private val h = LongArray(n * 2) { Long.MIN_VALUE } var size = 1 private fun siftUp(i: Int): Int { return if (h[i] > h[i / 2] && i != 1) { val tmp = h[i] h[i] = h[i / 2] h[i / 2] = tmp siftUp(i / 2) } else { i } } private fun siftDown(i: Int): Int { val max = if (h[i * 2] > h[i * 2 + 1]) i * 2 else i * 2 + 1 return if (h[max] > h[i]) { val tmp = h[i] h[i] = h[max] h[max] = tmp siftUp(max) } else { i } } fun add(v: Long) { h[size] = v siftUp(size) size++ } fun remove(i: Int) { h[i] = h[size - 1] h[size - 1] = 0 siftDown(i) } fun get(i: Int): Long { if (i > size) { System.err.print("HeapIndexOutOfBoundsException: $i from ${size()}") System.exit(-1) } return h[i] } fun set(i: Int, x: Long): Int { if (i > size) { System.err.print("HeapIndexOutOfBoundsException: $i from ${size()}") System.exit(-1) } h[i] = x val newDown = siftDown(i) val newUp = siftUp(i) return if (newDown != i) newDown else newUp } fun size() = size - 1 fun peek() = h[1] fun poll() { h[1] = h[size - 1] h[size - 1] = 0 siftDown(1) } override fun toString(): String { val res = StringBuilder() for (i in 1..size()) res.append("${h[i]} ") return res.toString() } data class Cargo(val t: Long, val l: Long, val i: Int) : Comparable<Cargo> { override fun compareTo(other: Cargo): Int = t.compareTo(other.t) } data class Block(val i: Int, val level: Int) : Comparable<Block> { override fun compareTo(other: Block): Int = level.compareTo(other.level) } fun `in`(x: Int, y: Int): Boolean = x in 0 until n && y in 0 until m class FastScanner(b: BufferedReader) { var br: BufferedReader = b var st = StringTokenizer("") var sp = "" var type: Boolean = false fun nextlong(): Long { return if (!type) { if (st.hasMoreTokens()) { st = StringTokenizer(br.readLine()) } java.lang.Long.parseLong(st.nextToken()) } else { if (!st.hasMoreTokens()) { st = StringTokenizer(sp) } java.lang.Long.parseLong(st.nextToken()) } } fun nextInt(): Int { return if (!type) { if (!st.hasMoreTokens()) { st = StringTokenizer(br.readLine()) } Integer.parseInt(st.nextToken()) } else { if (!st.hasMoreTokens()) { st = StringTokenizer(sp) } Integer.parseInt(st.nextToken()) } } fun next(): String = if (!type) { if (!st.hasMoreTokens()) { st = StringTokenizer(br.readLine()) } st.nextToken() } else { if (!st.hasMoreTokens()) { st = StringTokenizer(sp) } st.nextToken() } fun nextLine(): String { return br.readLine() } } import java.io.File import java.io.PrintWriter import java.util.Scanner fun main(args: Array<String>) { val sc = Scanner(System.`in`) val pw = PrintWriter(System.out) val n = sc.nextInt() val mass = LongArray(n) for (i in 0 until n) mass[i] = sc.nextLong() val sums = SequencesTree(mass) while (sc.hasNext()) { val t = sc.next() if (t == "sum") { pw.println(sums[sc.nextInt() - 1, sc.nextInt() - 1]) } else { sums.set(sc.nextInt() - 1, sc.nextLong()) } } pw.close() } init { build(0, a.size - 1, 1) } fun build(l: Int, r: Int, v: Int) { if (l == r) { t[v] = a[l] return } val m = (l + r) / 2 build(l, m, v * 2) build(m + 1, r, v * 2 + 1) t[v] = t[v * 2] + t[v * 2 + 1] } operator fun get(l: Int, r: Int, v: Int = 1, nl: Int = 0, nr: Int = a.size - 1): Long { if (l > r) return 0 if (nl == l && nr == r) return t[v] val m = (nl + nr) / 2 return get(l, Math.min(r, m), v * 2, nl, m) + get(Math.max(m + 1, l), r, v * 2 + 1, m + 1, nr) } fun set(i: Int, value: Long, v: Int = 1, l: Int = 0, r: Int = a.size - 1) { if (l == r) { t[v] = value return } val m = (l + r) / 2 if (i <= m) { set(i, value, v * 2, l, m) } else { set(i, value, v * 2 + 1, m + 1, r) } t[v] = t[v * 2] + t[v * 2 + 1] } } class ImplicitTreap { private int priority; private int size; long cost; private long sum; private ImplicitTreap left; private ImplicitTreap right; private static Random rand = new Random(); public ImplicitTreap(long c, int p) { cost = c; priority = p; recalc(this); } public ImplicitTreap(long c, int p, ImplicitTreap l, ImplicitTreap r) { cost = c; priority = p; left = l; right = r; recalc(this); } public ImplicitTreap() { recalc(this); } public static void recalc(ImplicitTreap t) { t.sum = getSum(t.left) + getSum(t.right) + t.cost * t.cost; t.size = getSize(t.left) + getSize(t.right) + 1; } static ImplicitTreap merge(ImplicitTreap L, ImplicitTreap R) { if (L == null) return R; if (R == null) return L; if (L.priority > R.priority) return new ImplicitTreap(L.cost, L.priority, L.left, merge(L.right, R)); else return new ImplicitTreap(R.cost, R.priority, merge(L, R.left), R.right); } static ImplicitTreap split(ImplicitTreap t, int x) { ImplicitTreap res = new ImplicitTreap(); if (t == null) return res; if (getSize(t.left) + 1 > x) { ImplicitTreap newRes = split(t.left, x); res.left = newRes.left; res.right = t; t.left = newRes.right; } else { ImplicitTreap newRes = split(t.right, x - getSize(t.left) - 1); res.right = newRes.right; res.left = t; t.right = newRes.left; } recalc(res); recalc(t); return res; } static ImplicitTreap add(ImplicitTreap t, long c, int i) { if (t == null) return new ImplicitTreap(c, rand.nextInt()); ImplicitTreap newT = split(t, i); ImplicitTreap toAdd = new ImplicitTreap(c, rand.nextInt()); return merge(newT.left, merge(toAdd, newT.right)); } static ImplicitTreap remove(ImplicitTreap t, int i) { ImplicitTreap newR = split(t, i + 1); ImplicitTreap newL = split(newR.left, i); return merge(newL.left, newR.right); } static ImplicitTreap get(ImplicitTreap t, int i) { if (t == null) return null; int sizeLeft = getSize(t.left); if (sizeLeft == i) return t; if (sizeLeft < i) return get(t.right, i - sizeLeft - 1); else return get(t.left, i); } static void update(ImplicitTreap t, int i, long v) { if (t == null) return; int sizeLeft = getSize(t.left); if (sizeLeft == i) { t.cost += v; return; } if (sizeLeft < i) update(t.right, i - sizeLeft - 1, v); else update(t.left, i, v); recalc(t); } static long getSum(ImplicitTreap t) { if (t != null) return t.sum; else return 0; } static int getSize(ImplicitTreap t) { if (t != null) return t.size; else return 0; } static String toString(ImplicitTreap t) { if (t == null) return ""; else return toString(t.left) + " " + t.cost + " " + toString(t.right); } } import java.io.BufferedReader import java.io.File import java.io.FileReader import java.io.PrintWriter import java.lang.Math.* import java.util.* fun main(args: Array<String>) { val sc = FastScanner(File("hall.in")) val pw = PrintWriter("hall.out") val a = sc.nextLong() val b = sc.nextLong() var c = sc.nextLong() if (c % 2 == 1L) c++ val d = sc.nextLong() var cnt = 0L if (a < 1000 && b < 1000) { val was = HashSet<Pair<Int, Int>>() for (f in 1..1000) for (s in 1..1000) if ((f + s) * 2 in c..d && (f * s) in a..b && !was.contains(f to s) && !was.contains(s to f)) { cnt++ was.add(f to s) was.add(s to f) } }else { val sqr = sqrt(b.toDouble()).toLong() for (i in 1..sqr) { val l1 = (a + i - 1) / i val r1 = b / i val l2 = max(i, c / 2 - i) val r2 = max(i, d / 2 - i) cnt += max(min(r1, r2) - max(i, max(l1, l2)) + 1, 0) } } pw.println(cnt) pw.close() } class FastScanner(file: File) { private val _br = BufferedReader(FileReader(file)) private var _st = StringTokenizer("") fun next(): String { if (!_st.hasMoreTokens()) _st = StringTokenizer(_br.readLine()) return _st.nextToken() } fun nextInt() = next().toInt() fun nextLong() = next().toLong() } import java.io.File import java.io.PrintWriter import java.util.* fun main(args: Array<String>) { val sc = Scanner(File("prizes.in")) val pw = PrintWriter("prizes.out") val n = sc.nextInt() val k = sc.nextInt() val prizes = LongArray(n) val prefix = LongArray(n) val sufix = LongArray(n) for (i in 0 until n) prizes[i] = sc.nextLong() var sum: Long = 0 var maxsum: Long = 0 for (i in 0 until n) { when { i + 1 < k -> { prefix[i] = 0 sum += prizes[i] } i + 1 == k -> { sum += prizes[i] maxsum = sum prefix[i] = maxsum } else -> { sum += prizes[i] sum -= prizes[i - k] maxsum = Math.max(sum, maxsum) prefix[i] = maxsum } } } sum = 0 maxsum = 0 run { var i = n - 1 var count = 1 while (i >= 0) { when { count < k -> { sufix[i] = 0 sum += prizes[i] } count == k -> { sum += prizes[i] maxsum = sum sufix[i] = maxsum } else -> { sum += prizes[i] sum -= prizes[i + k] maxsum = Math.max(sum, maxsum) sufix[i] = maxsum } } i-- count++ } } var min = java.lang.Long.MAX_VALUE for (i in 0..n - k) { val bob: Long = when (i) { 0 -> sufix[i + k] n - k -> prefix[i - 1] else -> Math.max(sufix[i + k], prefix[i - 1]) } min = Math.min(min, bob) } pw.println(min) pw.close() } import java.io.* import java.lang.Math.max import java.util.StringTokenizer fun main(args: Array<String>) { val sc = FastScanner(BufferedReader(FileReader("strange.in"))) val pw = PrintWriter("strange.out") val s = sc.next() val letters = arrayListOf<Pair<Long, Char>>() var col = 1L for (i in 1 until s.length) { if (s[i] == s[i - 1]) col++ else { letters.add(col to s[i - 1]) col = 1 } } letters.add(col to s.last()) val one = hashMapOf<Char, Long>() for (i in letters) one[i.second] = max(one.getOrDefault(i.second, 0), i.first) val two = HashMap<Triple<Char, Char, Long>, Long>() for (i in 1 until letters.size) { for (j in 1..letters[i - 1].first) { val key = Triple(letters[i - 1].second, letters[i].second, j) two[key] = max(two.getOrDefault(key, 0), letters[i].first) } } var sum = 0L for (v in two.values) sum += v for (v in one.values) sum += v pw.println(sum) pw.close() } class FastScanner(b: BufferedReader) { var br: BufferedReader = b var st = StringTokenizer("") var sp = "" var type: Boolean = false @Throws(IOException::class) fun nextlong(): Long { return if (!type) { if (!st.hasMoreTokens()) { st = StringTokenizer(br.readLine()) } (st.nextToken()).toLong() } else { if (!st.hasMoreTokens()) { st = StringTokenizer(sp) } (st.nextToken()).toLong() } } @Throws(IOException::class) fun nextInt(): Int { return if (!type) { if (!st.hasMoreTokens()) { st = StringTokenizer(br.readLine()) } Integer.parseInt(st.nextToken()) } else { if (!st.hasMoreTokens()) { st = StringTokenizer(sp) } Integer.parseInt(st.nextToken()) } } @Throws(IOException::class) operator fun next(): String = if (!type) { if (!st.hasMoreTokens()) { st = StringTokenizer(br.readLine()) } st.nextToken() } else { if (!st.hasMoreTokens()) { st = StringTokenizer(sp) } st.nextToken() } @Throws(IOException::class) fun nextLine(): String { return br.readLine() } } import java.* import java.io.* import java.util.Arrays import java.util.Scanner import java.util.StringTokenizer var br: BufferedReader? = null var st = StringTokenizer("") fun main(args: Array<String>) { br = BufferedReader(FileReader("space.in")) val pw = PrintWriter("space.out") val n = nextlong() val a = nextlong() val b = nextlong() val w = nextlong() val h = nextlong() var l: Long = 0 var r = Math.min(w, h) / 2 + 10 while (l != r - 1) { val m = (l + r) / 2 val a2 = a + m * 2 val b2 = b + m * 2 val colw1 = w / b2 val colh1 = h / a2 val colw2 = w / a2 val colh2 = h / b2 if (Math.max(colw2 * colh2, colw1 * colh1) < n) { r = m } else { l = m } } pw.print(l) pw.close() } fun nextlong(): Long { while (!st.hasMoreTokens()) { st = StringTokenizer(br!!.readLine()) } return java.lang.Long.parseLong(st.nextToken()) } |
Комментарии