/** * TLE submission that uses an array of longs and bit operations to track which * locations are have been visited for each passenger. * * Time complexity O(n*n/63) */ fun main() { var numPassengers = readln().toInt() var steps = numPassengers * 2 var locationSequence = IntArray(steps) var pickupIndex = IntArray(numPassengers) { -1 } var dropoffIndex = IntArray(numPassengers) var locationMax = 0 for (index in 0..numPassengers * 2 - 1) { val (passenger, location) = readln().split(" ").map { it.toInt() } locationSequence[index] = location - 1 if (pickupIndex[passenger - 1] == -1) { pickupIndex[passenger - 1] = index } else { dropoffIndex[passenger - 1] = index } if (location > locationMax) { locationMax = location } } var visitedSize = (locationMax)/63; if (visitedSize * 63 < 2*numPassengers) { visitedSize++ } var complaints = 0L for (passengerIndex in 0..numPassengers - 1) { var locationsVisited = LongArray(visitedSize) for (index in pickupIndex[passengerIndex]..dropoffIndex[passengerIndex]) { var location = locationSequence[index] var locationsVisitedIndex = location / 63 var locationBit = location % 63 if ((locationsVisited[locationsVisitedIndex] and (1L shl locationBit)) == 0L) { locationsVisited[locationsVisitedIndex] = locationsVisited[locationsVisitedIndex] or (1L shl locationBit); } else { complaints += 1; } } } println(complaints) }