/** * The problem can be reduced to answering a range query for each passenger. * The range query is "How many distinct locations are visited between the * pickup and dropoff, inclusive". The number of complaints from that passenger * will be equal to the size of the interval minus the number of distinct * locations. * * We can answer the distinct location queries using Mo's algorithm. * * This submission get WA because of integer overflow. * * @author Finn Lidbetter * Time complexity: O(N * sqrt(N)) */ import kotlin.math.* fun main() { var numPassengers = readln().toInt() var steps = numPassengers * 2 var locationSequence = IntArray(steps) var pickupIndex = IntArray(numPassengers) { -1 } var dropoffIndex = IntArray(numPassengers) for (index in 0..numPassengers * 2 - 1) { val (passenger, location) = readln().split(" ").map { it.toInt() } locationSequence[index] = location if (pickupIndex[passenger - 1] == -1) { pickupIndex[passenger - 1] = index } else { dropoffIndex[passenger - 1] = index } } var intervals = Array(numPassengers) { null } for (passengerIndex in 0..numPassengers - 1) { intervals[passengerIndex] = Interval( pickupIndex[passengerIndex], dropoffIndex[passengerIndex] ) } var bucketSize = kotlin.math.sqrt(steps.toDouble()).toInt() var numBuckets = steps / bucketSize if (numBuckets * bucketSize < steps) { numBuckets++ } var intervalBuckets = Array>(numBuckets) { mutableListOf() } for (interval in intervals) { var bucketIndex = bucketIndex(interval!!.lo, bucketSize) intervalBuckets[bucketIndex].add(interval!!) } for (intervalBucket in intervalBuckets) { intervalBucket.sort() } var complaints = 0 for (intervalBucket in intervalBuckets) { if (intervalBucket.size == 0) { continue } var currentLo = intervalBucket.get(0).lo var currentHi = currentLo var currentDistinct = 1 var locationCounts = IntArray(steps + 1) { 0 } locationCounts[locationSequence[currentLo]]++ for (interval in intervalBucket) { while (currentHi < interval.hi) { currentHi++ locationCounts[locationSequence[currentHi]]++ if (locationCounts[locationSequence[currentHi]] == 1) { currentDistinct++ } } while (currentLo < interval.lo) { locationCounts[locationSequence[currentLo]]-- if (locationCounts[locationSequence[currentLo]] == 0) { currentDistinct-- } currentLo++ } while (currentLo > interval.lo) { currentLo-- locationCounts[locationSequence[currentLo]]++ if (locationCounts[locationSequence[currentLo]] == 1) { currentDistinct++ } } complaints += (interval.hi - interval.lo + 1) - currentDistinct } } println(complaints) } fun bucketIndex(index: Int, bucketSize: Int): Int { return index / bucketSize } class Interval(val lo: Int, val hi: Int): Comparable { override operator fun compareTo(other: Interval): Int { if (this.hi == other.hi) { return this.lo - other.lo } return this.hi - other.hi } }