Submission #3054164

---

Source Code Expand

class Bit(object):
    def __init__(self,l):
        self.size = l
        self.bit = [0] * (self.size+1)

    def query(self, i):
        s = 0
        while i > 0:
            s = max(s,self.bit[i])
            i -= i & -i
        return s

	# instead add... 
    def update(self, i, x):
        while i <= self.size:
            self.bit[i] = max(x,self.bit[i])
            i += i & -i

    def __str__(self):
        return str(self.bit)

N = int(input())
box = [0 for _ in range(N)]
for i in range(N):
	w, h = map(int,input().split())
	box[i] = (i,w,h)
# sort by h_i in ordinal and w_i in reverse
box.sort(key = lambda x: -x[1])
box.sort(key = lambda x: x[2])
dp = [0 for _ in range(N)]
bit = Bit(10**5)
for i in range(N):
 	dp[i] = bit.query(box[i][1]-1) + 1
 	bit.update(box[i][1],dp[i])
# 	print("%d:%s:%s" % (i,dp,bit))
print(max(dp))

Submission Info

Judge Result