Informatica Online Judge

  친한 친구들 [1029 / 0405]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 12   Total Tried : 20


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (31st 정현수)]

Background

경곽의 학생들은 모두 친한 친구들끼리만 계속 친한 경향이 있다.

때문에 모든 학생들이 b개의 파 중 단 한 개의 파에 속한다.

아침점호 때 a명의 학생이 한 줄로 산책을 하는데 같은 파에 속한 학생의 거리가 c 이하인 경우, 이들은 매우 시끄럽게 떠든다.

이를 매우 언짢게 여긴 사감선생님은 떠드는 아이들의 쌍이 모두 몇 쌍인지 알아보고 싶어졌다.

이를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 학생의 수 a, 파의 수 b, 떠들 수 있는 최대거리 c가 공백으로 구분되어 주어진다.
두 번째 줄에는 i번째 할생이 속한 파의 번호 wi가 공백으로 구분되어 입력된다.

[입력값의 정의역]
1<=a<=10000000
0<=b<=a
0<=c<=a
1<=wi<=b

[Sub Task Info]
#1 : a <= 20,000
#2 : a <= 100,000
#3 : a <= 400,000
#4 : 추가 제한 조건 없음.

Output

떠드는 아이들의 쌍의 수를 출력한다.

IO Example

입력
7 4 3
1 2 1 3 2 4 3

출력
3

* 설명 : 다음 그림과 같다.



Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]