fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6.  
  7. /*```````````````````````````****Defined macros*****``````````````````````````*/
  8. const int mod = 1e9 + 7;
  9. #define ll long long
  10. #define endl "\n"
  11. #define ull unsigned long long
  12. #define pb push_back
  13. #define yes cout<<"YES"<<endl;
  14. #define no cout<<"NO"<<endl;
  15. #define set_bits __builtin_popcountll
  16. #define all(x) x.begin(), x.end()
  17. #define vll vector<ll>
  18. #define vii vector<int>
  19. #define tll takein<ll>
  20. #define tii takein<int>
  21.  
  22. template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  23. template <class K, class V> using ordered_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
  24.  
  25. /*```````````````````````````````//DEBUGGER``````````````````````````````````*/
  26. #ifndef ONLINE_JUDGE
  27. #define _debug(x) cerr << #x <<" "; _print(x); cerr << endl;
  28. #else
  29. #define _debug(x)
  30. #endif
  31. template<typename T>void _print(T x){cerr<<x;}
  32. template <class T, class V> void _print(pair <T, V> p);
  33. template <class T> void _print(vector <T> v);
  34. template <class T> void _print(set <T> v);
  35. template <class T, class V> void _print(map <T, V> v);
  36. template <class T> void _print(multiset <T> v);
  37. template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.first); cerr << ","; _print(p.second); cerr << "}";}
  38. template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  39. template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  40. template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  41. template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
  42. template< typename T> vector<T> takein(int n){vector<T>A;for(int i=0;i<n;i++){T x;cin>>x;A.push_back(x);}return A;}
  43. template< typename T> vector<T> presum(vector<T>&A){vector<T>ans(A.size(),0);ans[0]=A[0];for(int i=1;i<A.size();i++){ans[i]=ans[i-1]+A[i];}return ans;}
  44. template <typename T> void idxocc(vector<T>A,vector<vector<T>>idx){for(int i = 0; i < A.size(); i++) {T a;cin >> a;idx[a].push_back(i);}}
  45. template<typename T>void print_arr(vector<T>ans){for(auto i:ans){cout<<i<<" ";}cout<<endl;}
  46. ll fastExp(int N,int R){ll ans = 1;while (R > 0){if (R % 2 == 1){ans = (ans* 1LL * N);}N = (N *1LL* N);R = R >> 1;}return ans;}
  47. /*```````````````````````````````//predefined f(x)``````````````````````````````````*/
  48.  
  49. int x_Nx = 1e5 + 1;
  50. vector<bool> prime(x_Nx, 1);
  51. void primality(){prime[1] = prime[0] = 0;for (int i = 2; i * i <= x_Nx; i++){if (prime[i] == 1){for (int j = i * i; j <= x_Nx; j = j + i){prime[j] = 0;}}}return;}
  52. // use binsea snippet for Binary_search code
  53.  
  54.  
  55. //ceil(A/B)=(A+B-1)/B
  56. //log2(A)==Highest set bit in A
  57. /*```````````````````````````````//solution``````````````````````````````````*/
  58.  
  59. void solve()
  60. {
  61.     //solve the question here
  62.     int n,m;
  63.     cin>>n>>m;
  64.     ll k;
  65.     cin>>k;
  66.     map<ll,ll>mp;
  67.     for(int i=0;i<n;i++){
  68.         ll x;
  69.         cin>>x;
  70.         mp[x]++;
  71.     }
  72.     vll B=tll(m);
  73.     int ans=0;
  74.     for(int i=0;i<m;i++){
  75.         auto it=mp.lower_bound(B[i]-k);
  76.         if(it!=mp.end()){
  77.             ll x=it->first;
  78.             if(x<=B[i]+k)
  79. {            mp[x]--;
  80.             if(mp[x]==0){
  81.                 mp.erase(x);
  82.             }
  83.             ans++;
  84. }
  85.         }
  86.  
  87.     }   
  88.     cout<<ans<<endl;
  89. }
  90.  
  91.  
  92. int main() {
  93.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  94.     srand(chrono::high_resolution_clock::now().time_since_epoch().count());
  95.     /*#ifndef ONLINE_JUDGE
  96.     freopen("Error.txt", "w", stderr);
  97.     #endif*/
  98.     int t=1;
  99.     //cin>>t;
  100.     while(t--)
  101.     {
  102.         solve();
  103.     }
  104.     return 0;
  105. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/nSFXWD
language:
C++ (gcc 8.3)
created:
37 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!