oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

overtaking Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

overtaking.html

Problem Description

Rar the Cat has invited N of his animal friends for a race. As some species can naturally move faster than others, Rar the Cat decided to normalise their differences by allocating different starting positions to each animal. The ith animal will start at position Pi, the higher the animal's position, the earlier it is in the line up and the closer it is to the finishing line.

The race has since concluded and Rar the Cat has recorded the total time (in seconds) of which of his animal friends have taken to complete the race from their respective starting positions. The time taken for the ith animal is Ti.

Given these values, Rar the Cat is interested in how many over-taking has taken place during the race, assuming that all of his animal friends run at a constant speed throughout the race. In other words, they do not slow down or speed up in the middle of the race.

An animal A is said to have over-taken another animal B where at some point in time, A was a further distance away from the finishing point than B but caught up and A ended up being in a shorter distance away from the finishing point than B at a later point in time.

Do note that based on the above definition, when 2 animals share a starting position or complete the race at the same time, they are deemed to have not over-taken each other.

Input

The first line of input will contain one integer, N, the number of animals participating in the race.

The second line of input will contain N integers, the ith integer will be Pi.

The third line of input will also contain N integers, the ith integer will be Ti.

Output

The output should contain one integer, the total number of over-takings in the entire race.

Limits

For all testcases, 0 ≤ Pi ≤ 109, 0 ≤ Ti ≤ 109.

Subtask 1 (9%): 1 ≤ N ≤ 2.

Subtask 2 (39%): 1 ≤ N ≤ 2000.

Subtask 3 (32%): 1 ≤ N ≤ 200000. However, no two animals share the same starting position and no two animals end at the same time.

Subtask 4 (20%): 1 ≤ N ≤ 200000.

Subtask 5 (0%): Sample Testcases

Sample Testcase 1

Input

2
0 10
10 20

Output

1

Explanation

Animal 1 started further away from the finishing line, yet finished earlier than Animal 2. Hence, Animal 1 must have overtaken Animal 2 in the middle of the race.

Sample Testcase 2

Input

5
1 2 3 4 5
30 20 30 20 10

Output

1

Explanation

Animal 2 started further away from the finishing line, yet finished earlier than Animal 3. Hence, Animal 2 must have overtaken Animal 3 in the middle of the race.

Sample Testcase 3

Input

5
1 2 3 4 5
10 20 30 40 50

Output

10

Explanation

Animal 1 started the furthest away from the finishing line, yet finished earlier than Animals 2, 3, 4 and 5. Hence, Animal 1 must have overtaken all 4 other animals during the race.

Animal 2 started further from the finishing line as compared to Animals 3, 4 and 5. Yet, Animal 2 finished earlier than Animals 3, 4 and 5. Hence, Animal 2 must have overtaken these 3 animals during the race.

A similar argument holds for Animal 3 compared to Animals 4 and 5. Hence, Animal 3 must have overtaken 2 animals during the race.

Animal 4 started further away from the finishing line, yet finished earlier than Animal 5. Hence, Animal 4 must have overtaken Animal 5 in the middle of the race.

In total, there are 10 over-takings, 4 by Animal 1, 3 by Animal 2, 2 by Animal 3 and 1 by Animal 1.

Tags

Sorting

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
19131s256MBMinimum
239431s256MBMinimum
332161s256MBMinimum
420941s256MBMinimum
5031s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o overtaking -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.