쉬운 정렬 문제

면접 대비

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

요약
배열과 K가 주어질 때 값 차이가 K 이하인 인접한 두 원소만 교환할 수 있다. 배열을 오름차순으로 정렬할 수 있는지 판별한다.
난이도

보통10점 중 6점

유형
정렬, 유니온 파인드, 그리디, 배열
정답자
아직 제출이 없습니다

문제

정수 NN개로 이루어진 배열 AA와 정수 KK가 주어진다. 다음 연산을 00회 이상 원하는 만큼 실행할 수 있다.

  • 배열에서 인접한 두 원소를 골라 교환한다. 단, 두 원소의 값의 차이가 KK 이하여야 한다.

배열 AA를 오름차순으로 정렬할 수 있는지 판별해 보자.

입력

첫째 줄에 정수 NN과 KK가 주어진다. (1≤N≤200,000;0≤K≤109)(1 \le N \le 200\\, 000;0 \le K \le 10^{9})

둘째 줄에 배열 AA의 원소 A_1,⋯ ,A_NA\_1, \cdots, A\_N이 공백으로 구분되어 주어진다. (0≤A_i≤109)(0 \le A\_i \le 10^{9})

출력

정렬할 수 있다면 YES를, 그렇지 않다면 NO를 출력한다.

예제2

  1. 예제 1

    입력
    5 3
    3 2 5 7 4
    
    예상 출력
    YES
    
  2. 예제 2

    입력
    3 0
    3 2 1
    
    예상 출력
    NO