Guest User

898D

a guest
Dec 16th, 2017
257
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.77 KB | None | 0 0
  1. /*
  2.     ##############################
  3.     ## Author: Pratyush Gaurav ###
  4.     ## College: NIT ROURKELA #####
  5.     ##############################
  6. */
  7. #include <bits/stdc++.h>
  8.  
  9. using namespace std;
  10.  
  11. typedef long long/*--------------------*/lli;
  12. typedef long double/*------------------*/ld;
  13. typedef unsigned long long/*-----------*/ulli;
  14. typedef pair<lli, lli >/*--------------*/plli;
  15. typedef vector<plli >/*----------------*/vplli;
  16.  
  17. #define rep(i,a)/*---------------------*/for(i = 0 ; i < a ; i++)
  18. #define repr(i,a)/*--------------------*/for(i = a ; i >= 0 ; i--)
  19. #define REP(i,a,b)/*-------------------*/for(i = a ; i <= b ; i++)
  20. #define REPR(i,a,b)/*------------------*/for(i = a ; i >= b ; i--)
  21.  
  22. #define scan(N)/*----------------------*/scanf("%lld",&N)
  23. #define print(N)/*---------------------*/printf("%lld\n",N)
  24. #define scan2(N1,N2)/*-----------------*/scanf("%lld %lld",&N1,&N2)
  25. #define print2(N1,N2)/*----------------*/printf("%lld %lld",N1,N2)
  26. #define scan3(N1,N2,N3)/*--------------*/scanf("%lld %lld %lld",&N1,&N2,&N3)
  27. #define print3(N1,N2,N3)/*-------------*/printf("%lld %lld %lld",N1,N2,N3)
  28.  
  29. #define lb/*---------------------------*/lower_bound
  30. #define ub/*---------------------------*/upper_bound
  31. #define pb/*---------------------------*/push_back
  32. #define popb/*-------------------------*/pop_back
  33.  
  34. #define mem(a,b)/*---------------------*/memset(a,b,sizeof(a))
  35. #define opt/*--------------------------*/ios_base::sync_with_stdio(false);cin.tie(NULL);
  36. #define sz/*---------------------------*/size()
  37.  
  38. #define MP/*---------------------------*/make_pair
  39. #define bs/*---------------------------*/binary_search
  40. #define gcd(a, b)/*--------------------*/__gcd(a, b)
  41. #define lcm(a, b)/*--------------------*/((a)*((b)/gcd(a,b)))
  42. #define sqr(x)/*-----------------------*/(x)*(x)
  43. #define all(a)/*-----------------------*/a.begin(),a.end()
  44.  
  45. #define ff/*---------------------------*/first
  46. #define ss/*---------------------------*/second
  47.  
  48. #define endl/*-------------------------*/'\n'
  49. #define inf/*--------------------------*/(lli)2000000000000
  50. #define MOD/*--------------------------*/(lli)1000000007
  51. #define MAXN/*-------------------------*/1000005
  52.  
  53. template<class T> bool is_prime(T n)
  54. {
  55.     if((n%2 == 0 and n > 2) or n < 2 )
  56.         return false;
  57.     for(T i = 3; i*i <= n ; i += 2)
  58.     {
  59.         if( n % i == 0)
  60.             return false;
  61.     }
  62.     return true;
  63. }
  64. lli power(lli a,lli b)
  65. {
  66.     lli value;
  67.     if(!b)
  68.         return 1;
  69.     else if(b%2==0)
  70.     {
  71.         value = power(a,b/2)%MOD;
  72.         return (value * value)%MOD;
  73.     }
  74.     else
  75.     {
  76.         value = power(a,b/2)%MOD;
  77.         return ((a*value)%MOD*(value))%MOD;
  78.     }
  79. }
  80. lli tree[4*MAXN];
  81. void update(lli node,lli start,lli end,lli idx,lli val)
  82. {
  83.     if(start == end)
  84.         tree[node] = val;
  85.     else
  86.     {
  87.         lli mid = (start+end) >> 1;
  88.         if(idx <= mid)
  89.             update(2*node,start,mid,idx,val);
  90.         else
  91.             update(2*node+1,mid+1,end,idx,val);
  92.         tree[node] = tree[2*node] + tree[2*node+1];
  93.     }
  94. }
  95. lli query(lli node,lli start,lli end,lli l,lli r)
  96. {
  97.     if(start > end or end < l or start > r)
  98.         return 0;
  99.     if(start >= l and end <= r)
  100.         return tree[node];
  101.     lli mid = (start + end) >> 1;
  102.     return (query(2*node,start,mid,l,r) + query(2*node+1,mid+1,end,l,r));
  103. }
  104. int main()
  105. {
  106.     opt;
  107.     lli n,m,k;
  108.     scan3(n,m,k);
  109.     lli v[n];
  110.     lli i,ans = 0;
  111.     REP(i,1,n) scan(v[i]);
  112.     sort(v+1,v+n+1);
  113.     lli maxi = v[n];
  114.     REP(i,1,n)
  115.     {
  116.         update(1,1,maxi,v[i],1);
  117.     }
  118.     REP(i,1,n)
  119.     {
  120.         lli tmp = query(1,1,maxi,max(1LL,v[i]-m+1),v[i]);
  121.         if(tmp >= k)
  122.         {
  123.             ans++;
  124.             //print(v[i]);
  125.             update(1,1,maxi,v[i],0);
  126.         }
  127.         //print(query(1,1,maxi,v[i],v[i]));
  128.     }
  129.     //print(query(1,1,n,3,6));
  130.     print(ans);
  131.     return 0;
  132. }
Add Comment
Please, Sign In to add comment