AtCoder Regular Contest 133 B

https://atcoder.jp/contests/arc133/tasks/arc133_b

解説にあるように、まず(i, j)を(i, -j)をキーにソートします。しかし、PyPyではこれが遅いんですね。適当なN=200000の列で2.7秒かかりました。
これを、iが小さい方から、iが同じjを降順にソートしてextendしていけば速いです。10倍の速度になりました。

そして、jの最長増加部分列を取ります。例えば、例2で考えてみましょう。

5 4 3 2 1 4 2 3 2 1

この最長増加部分列は、

        1   2 3    

ですね。ちょっと考えればこれは簡単にDPで分かります。


ここでは列のインデックスですが、数値にしてもよいです。そうするとdpは、

0 0 0 0 0
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 2 1 2 1
1 2 3 2 1
1 2 3 2 1
1 2 3 2 1

と変化していきます。dpの最後で最大のものが最長増加部分列の長さです。
ネックは、より小さいでで最も大きいものを見つけることですが、これは木で実現できます。特にBITだと高速に実現できます。ただ、この問題はよいですが、一般的にはこうはできませんね。値を振りなおせばよいですが。

# coding: utf-8
# Dividing Subsequence

from itertools import *
from collections import Counter
import sys


#################### library ####################

def read_int():
    return int(raw_input())

def read_list():
    return list(map(int, raw_input().split()))


#################### BIT ####################

class BIT:
    def __init__(self, N):
        self.N = N
        self.v = [0] * (N+1)
    
    def max_value(self, i):
        m = 0
        j = i
        while j > 0:
            m = max(m, self.v[j])
            j -= j & -j
        return m
    
    def update(self, i, n):
        j = i
        while j <= self.N:
            if self.v[j] < n:
                self.v[j] = n
            j += j & -j


#################### process ####################

def read_input():
    N = read_int()
    P = read_list()
    Q = read_list()
    return (P, Q)

def F(P, Q):
    def make_edges(P, Q):
        N = len(P)
        dic = [0] * (N+1)
        for j, q in enumerate(Q, 1):
            dic[q] = j
        
        v = []
        for i in range(N):
            p = P[i]
            w = sorted((dic[q] for q in range(p, N+1, p)), reverse=True)
            v.extend(w)
        return v
    
    def bit_length(n):
        length = 0
        while n > 0:
            length += 1
            n >>= 1
        return length
    
    edges = make_edges(P, Q)
    # 最長増加部分列
    tree = BIT(1 << bit_length(len(P)))
    for j in edges:
        length = tree.max_value(j-1)
        tree.update(j, length+1)
    return max(tree.v)


#################### main ####################

P, Q = read_input()
print F(P, Q)