Codeforces Round #448 (Div. 2)B
2574 단어 codeforces
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
While Vasya finished eating his piece of pizza, the lesson has already started. For being late for the lesson, the teacher suggested Vasya to solve one interesting problem. Vasya has an array a and integer x. He should find the number of different ordered pairs of indexes (i, j)such that ai ≤ aj and there are exactly k integers y such that ai ≤ y ≤ aj and y is divisible by x.
In this problem it is meant that pair (i, j) is equal to (j, i) only if i is equal to j. For example pair (1, 2) is not the same as (2, 1).
Input
The first line contains 3 integers n, x, k (1 ≤ n ≤ 105, 1 ≤ x ≤ 109, 0 ≤ k ≤ 109), where n is the size of the array a and x and k are numbers from the statement.
The second line contains n integers ai (1 ≤ ai ≤ 109) — the elements of the array a.
Output
Print one integer — the answer to the problem.
Examples
input
4 2 1
1 3 5 7
output
3
input
4 2 0
5 3 1 7
output
4
input
5 3 1
3 3 3 3 3
output
25
Note
In first sample there are only three suitable pairs of indexes — (1, 2), (2, 3), (3, 4).
In second sample there are four suitable pairs of indexes(1, 1), (2, 2), (3, 3), (4, 4).
In third sample every pair (i, j) is suitable, so the answer is 5 * 5 = 25.
자기가 진짜 못하네.
이 문제는 오랫동안 생각해서 다른 사람의 코드를 보고 나서야 알아차렸다
만족하는 구간을 찾아 각각 그와 인접한 하표를 찾아 상쇄하다
#include
using namespace std;
#define maxn 1000000+100
#define ll long long
long long a[maxn];
int main(){
ll n,k,x;
scanf("%lld%lld%lld",&n,&x,&k);
for(ll j=0;j
#include
using namespace std;
#define maxn 1000000+100
#define ll long long
long long a[maxn];
ll binary_search1(ll l,ll r,ll x){
while(l<=r){
int mid=(l+r)/2;
if(a[mid]>=x){
r=mid-1;
}
else l=mid+1;
}
return l;
}
int main(){
ll n,k,x;
scanf("%lld%lld%lld",&n,&x,&k);
for(ll j=0;j
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.