Chef and Reunion
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Today is the reunion of all chefs in the world. Our Chef wants to make this moment more happier. He arranged a mass wedding in this reunion. For this, he made a strange stage and drew two horizontal parallel lines on the stage. There are N unmarried male chefs in the reunion and he gave each male chef i an unique number Mi. Then all male chefs will stand in the first line drawn by Chef. But they will stand in increasing order of their number. That means chef with the lowest number will stand at the leftmost position of the line, then right to him would be the chef with the second lowest number and so on. Similarly, there are N female chefs in the reunion and Chef also gave each female chef j an unique number Fj (sequences Fj and Mi can have equal numbers). Then all female chefs will stand in the other line following the same rule(will stand in increasing order of the numbers) as the male chef.
Now chef will choose all the marriage pairs himself. He will select a female chef and a male chef (both of them have not selected before) and will draw a straight line between them. He calls this line a marriage line. He will do this for the rest of the chefs.
You will be given the N marriage lines; you have to find how many marriage line pairs intersect with each other.
First line contains a single integer N. The i-th line of the next N lines contain two space separated integers Mi and Fi, means there is a marriage line between male chef Mi and female chef Fi. No marriage line will be mentioned twice.
Output the number of marriage line pairs that intersect with each other on a single line.
- 1 ≤ N ≤ 100000 (105)
- 0 ≤ Mi, Fi ≤ 1000000000 (109)
Input: 3 2 3 3 6 5 4 Output: 1 Input: 4 5 12 10 11 11 9 30 1 Output: 6
Example case 1. Only marriage lines (3, 6) and (5, 4) intersect with each other.
Example case 2. All the marriage lines intersect with each other.
|Tags||bit, cook43, easy-medium, shiplu|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.