Block and escape! P16544


Statement
 

pdf   zip

html

You find yourself at one end of a narrow corridor…But there is something at the other end, what is it? OMG! It is a huge scary monster! And it is getting closer! What will you do?

You look around and you find a small computer. Since you are fast with computers (right?) and the monster is still far away (right?) you decide to take a look. It is the control system of the corridor’s gates! There are n vertical blast doors, with their left rail at ai meters from you, and their right rail at bi meters from you.

You have an idea! Let’s shut the blast doors so that the monster will have to break them all to get to you! So you order the control system to shut n doors. But you get this reply: “WA”.

Mmm…You cannot shut simultaneously two doors i and j that cross, that is, such that ai < aj but bi > bj. Ah well, you can probably shut some doors at least. For instance, this is one of the several optimum solutions (4 doors shut) for this corridor with 10 doors:





unit=0.15cm (80,16)

(8,0)0.0100(8,0) (16,0)0.0101(16,0) (24,0)0.0102(24,0) (32,0)0.0103(32,0) (40,0)0.0104(40,0) (48,0)0.0105(48,0) (56,0)0.0106(56,0) (64,0)0.0107(64,0) (72,0)0.0108(72,0) (80,0)0.0109(80,0)

(8,16)0.0110(8,16) (16,16)0.0111(16,16) (24,16)0.0112(24,16) (32,16)0.0113(32,16) (40,16)0.0114(40,16) (48,16)0.0115(48,16) (56,16)0.0116(56,16) (64,16)0.0117(64,16) (72,16)0.0118(72,16) (80,16)0.0119(80,16)

linewidth=2pt

(1,0)(106,0) (1,16)(106,16)

-1002 -1503 -1607 -1908

linewidth=0.5pt linestyle=dashed

-1100 -1206 -1305 -1409 -1701 -1804





The computer has an editor and a compiler, so you can try to make a program to find the maximum number of doors that can be shut. But hurry! The huge scary monster is getting closer…

Input

Input consists of several cases. Every case begins with the number of doors n, followed by a1, a2, …, an and b1, b2, …, bn. All the given numbers are integers. There are no repeated ai’s nor repeated bi’s. Assume 1 ≤ n ≤ 105 and 1 ≤ ai, bi ≤ 109.

Output

For every case, print the maximum number of doors that can be shut.

Public test cases

  • Input

    10
1 2 3 4 5 6 7 8 9 10
3 1 7 6 10 4 8 2 5 9
3
30 20 10
300 200 100
3
200 100 300
20 30 10

    Output

    4
3
1
    • Information
    Author
    Marçal Garolera
    Language
    English
    Official solutions
    C++
    User solutions
    C++