Assistant Ranking

시간 제한1초메모리 제한512 MB

요약
N개의 점 (a_i, b_i)와 한계 K가 주어질 때, a_i + K < a_j 또는 b_i + K < b_j이면 j가 i보다 낮은 순위가 아니어야 한다는 조건 아래 서로 다른 순위의 최대 개수를 구한다.
난이도

보통10점 중 7점

유형
정렬, 그리디, 이분 탐색, 동적 계획법
정답자
아직 제출이 없습니다

문제

The online retailer Amagoogsoftbook currently offers NN different so-called ``home assistants'', which it wants to recommend to its customers. For this recommendation, they wish to rank all the assistants. The quality of this ranking is not very important -- multiple assistants may even be assigned the same rank -- but they wish to maximize the number of distinct ranks assigned, to lessen the decision fatigue of their customers.

To ensure that the ranking is not completely arbitrary, they have collected for each assistant ii two measurements a_ia\_i and b_ib\_i -- the quality of the jokes the assistant can tell and how nice are the compliments the assistant is able to give (clearly these are the two most important aspects). These measurements are of course somewhat subjective, so we wish to ignore small differences in them. However, if for two given assistants ii and jj we have that a_i+K<a_ja\_i + K < a\_j or b_i+K<b_jb\_i + K < b\_j, the ranking of assistant jj must be the same or higher than the ranking of assistant ii. This rule may force two products to be given the same ranking, for example if an assistant ii gives much better puns than assistant jj, while assistant jj gives the superior self-esteem boosts.

What is the maximum number of distinct ranks, taken over all possible rankings?

입력

The first line contains the integers 1≤N≤100,0001 \le N \le 100\\,000 and 0≤K≤1090 \le K \le 10^9 -- the number of assistants and the measurement difference limit as described in the statement. The next line contains the NN integers a_1,a_2,…,a_Na\_1, a\_2, \dots, a\_N. The next line contains the NN integers b_1,b_2,…,b_Nb\_1, b\_2, \dots, b\_N.

All measurements are between 00 and 10910^9.

출력

Output a single integer: the maximum number of distinct ranks.

예제5

  1. 예제 1

    입력
    2 10
    1 12
    1 13
    
    예상 출력
    2
    
  2. 예제 2

    입력
    2 10
    1 5
    1 12
    
    예상 출력
    2
    
  3. 예제 3

    입력
    2 10
    1 5
    1 4
    
    예상 출력
    2
    
  4. 예제 4

    입력
    2 10
    1 5
    4 1
    
    예상 출력
    2
    
  5. 예제 5

    입력
    2 10
    1 12
    13 1
    
    예상 출력
    1