Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ##############################
- ## Author: Pratyush Gaurav ###
- ## College: NIT ROURKELA #####
- ##############################
- */
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long/*--------------------*/lli;
- typedef long double/*------------------*/ld;
- typedef unsigned long long/*-----------*/ulli;
- typedef pair<lli, lli >/*--------------*/plli;
- typedef vector<plli >/*----------------*/vplli;
- #define rep(i,a)/*---------------------*/for(i = 0 ; i < a ; i++)
- #define repr(i,a)/*--------------------*/for(i = a ; i >= 0 ; i--)
- #define REP(i,a,b)/*-------------------*/for(i = a ; i <= b ; i++)
- #define REPR(i,a,b)/*------------------*/for(i = a ; i >= b ; i--)
- #define scan(N)/*----------------------*/scanf("%lld",&N)
- #define print(N)/*---------------------*/printf("%lld\n",N)
- #define scan2(N1,N2)/*-----------------*/scanf("%lld %lld",&N1,&N2)
- #define print2(N1,N2)/*----------------*/printf("%lld %lld",N1,N2)
- #define scan3(N1,N2,N3)/*--------------*/scanf("%lld %lld %lld",&N1,&N2,&N3)
- #define print3(N1,N2,N3)/*-------------*/printf("%lld %lld %lld",N1,N2,N3)
- #define lb/*---------------------------*/lower_bound
- #define ub/*---------------------------*/upper_bound
- #define pb/*---------------------------*/push_back
- #define popb/*-------------------------*/pop_back
- #define mem(a,b)/*---------------------*/memset(a,b,sizeof(a))
- #define opt/*--------------------------*/ios_base::sync_with_stdio(false);cin.tie(NULL);
- #define sz/*---------------------------*/size()
- #define MP/*---------------------------*/make_pair
- #define bs/*---------------------------*/binary_search
- #define gcd(a, b)/*--------------------*/__gcd(a, b)
- #define lcm(a, b)/*--------------------*/((a)*((b)/gcd(a,b)))
- #define sqr(x)/*-----------------------*/(x)*(x)
- #define all(a)/*-----------------------*/a.begin(),a.end()
- #define ff/*---------------------------*/first
- #define ss/*---------------------------*/second
- #define endl/*-------------------------*/'\n'
- #define inf/*--------------------------*/(lli)2000000000000
- #define MOD/*--------------------------*/(lli)1000000007
- #define MAXN/*-------------------------*/1000005
- template<class T> bool is_prime(T n)
- {
- if((n%2 == 0 and n > 2) or n < 2 )
- return false;
- for(T i = 3; i*i <= n ; i += 2)
- {
- if( n % i == 0)
- return false;
- }
- return true;
- }
- lli power(lli a,lli b)
- {
- lli value;
- if(!b)
- return 1;
- else if(b%2==0)
- {
- value = power(a,b/2)%MOD;
- return (value * value)%MOD;
- }
- else
- {
- value = power(a,b/2)%MOD;
- return ((a*value)%MOD*(value))%MOD;
- }
- }
- lli tree[4*MAXN];
- void update(lli node,lli start,lli end,lli idx,lli val)
- {
- if(start == end)
- tree[node] = val;
- else
- {
- lli mid = (start+end) >> 1;
- if(idx <= mid)
- update(2*node,start,mid,idx,val);
- else
- update(2*node+1,mid+1,end,idx,val);
- tree[node] = tree[2*node] + tree[2*node+1];
- }
- }
- lli query(lli node,lli start,lli end,lli l,lli r)
- {
- if(start > end or end < l or start > r)
- return 0;
- if(start >= l and end <= r)
- return tree[node];
- lli mid = (start + end) >> 1;
- return (query(2*node,start,mid,l,r) + query(2*node+1,mid+1,end,l,r));
- }
- int main()
- {
- opt;
- lli n,m,k;
- scan3(n,m,k);
- lli v[n];
- lli i,ans = 0;
- REP(i,1,n) scan(v[i]);
- sort(v+1,v+n+1);
- lli maxi = v[n];
- REP(i,1,n)
- {
- update(1,1,maxi,v[i],1);
- }
- REP(i,1,n)
- {
- lli tmp = query(1,1,maxi,max(1LL,v[i]-m+1),v[i]);
- if(tmp >= k)
- {
- ans++;
- //print(v[i]);
- update(1,1,maxi,v[i],0);
- }
- //print(query(1,1,maxi,v[i],v[i]));
- }
- //print(query(1,1,n,3,6));
- print(ans);
- return 0;
- }
Add Comment
Please, Sign In to add comment