Number of overtakes
Practice
3.8 (16 votes)
Algorithms
Counting and arrangements
Divide And Conquer algorithm
Merge sort
Merge sort
Sorting
Problem
86% Success 3252 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

A race is organized among \(N\) horses of a kingdom. Every horse has a velocity (in \(m/sec\)) that is denoted by an array \(Velocity[\ ]\) where \(Velocity[i]\) represents the velocity of the \(i^{th}\) horse. The indexing of the array is 0-based.

All the horses are standing at different starting positions. The starting position of every horse is represented by an array \(pos[\ ]\) where \(pos[i]\) denotes the starting position of the \(i^{th}\) horse. The indexing of the array is 0-based. The \(pos[\ ]\) array is a permutation of integers \(1\) to \(N\). A horse who is standing at \(i\) position is considered to be ahead of the horse who is standing at position \(j\) if and only if \(i > j\).

The finish line of the race is \(10^{100000}\) meters ahead. An overtake occurs when horse A, whose starting position is less than horse B, finishes the race earlier than horse B. Your task is to determine the number of overtakes that has occurred during the race.

Input format

  • First line: An integer \(N\) denoting the number of horses that are participating in the race (\(2 \le N \le 10^5\))
  • Next line: \(N\) space-separated integers denoting the velocity of the \(i^{th}\) horse (\(1 \le Velocity[i] \le 10^7\))
  • Next line: \(N\) space-separated integers denoting the starting position of \(i^{th}\) horse (\(1 \le pos[i] \le N\))
    Note: Array is a permutation of integers \(1\) to \(N\) integers

Output format

Print a single integer denoting the number of overtakes that has occurred during the race.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
10 votes
Tags:
ApprovedEasyMathOpen
Points:30
21 votes
Tags:
AlgorithmsArraysEasyGreedy AlgorithmsMerge sortSorting
Points:30
330 votes
Tags:
ApprovedEasyReadySorting