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. #define ll long long
  5. using namespace __gnu_pbds;
  6. using namespace std;
  7. template <class T>
  8. using ordered_set = tree<T , null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update>;
  9. template <class T>
  10. using ordered_set1 = tree<T , null_type , greater<T> , rb_tree_tag , tree_order_statistics_node_update>;
  11. // less<T>/greater<T> = ascending/descending.
  12. // less_equal<>/greater_equal<> for ordered multiset
  13. // ordered_multiset note : s.find(), s.erase() don't work + s.upper_bound() and s.lower_bound() swap jobs;
  14. void fastIO(void) {
  15.     ios_base::sync_with_stdio(false);
  16.     cin.tie(NULL);
  17.     cout.tie(NULL);
  18.     //freopen("stdin", "r", stdin);
  19.     //freopen("stdout", "w", stdout);
  20. }
  21. struct animal{
  22.     ll index;
  23.     ll prednum;
  24.     ll preynum;
  25.     ll power;
  26. };
  27. bool cmp(animal x,ll b){
  28.     return x.power < b;
  29. }
  30. bool cmp3(animal x, animal y) {
  31.     return x.power < y.power;
  32. }
  33. bool cmp4(animal x, animal y) {
  34.     return x.index < y.index;
  35. }
  36. int main() {
  37.     fastIO();
  38.     ll n,a,b; cin>>n>>a>>b;
  39.     vector<animal> v(n);
  40.     for (ll i = 0; i<n; i++) {
  41.         cin>>v[i].power;
  42.         v[i].index=i;
  43.     }
  44.     sort(v.begin(),v.end(),cmp3);
  45.     for (ll i = 0; i<n; i++) {
  46.         //pred
  47.         auto predL = lower_bound(v.begin(),v.end(),v[i].power+a,cmp);
  48.         auto predR = lower_bound(v.begin(),v.end(),v[i].power+b,cmp);
  49.         v[i].prednum=predR-predL;
  50.         //prey
  51.         if (a>=v[i].power) {
  52.             v[i].preynum=0;
  53.             continue;
  54.         }
  55.         else {
  56.             auto preyR = lower_bound(v.begin(),v.end(),v[i].power-a,cmp);
  57.             if (preyR!=v.end() && v[preyR-v.begin()].power==v[i].power-a) preyR++;
  58.             auto preyL = lower_bound(v.begin(),v.end(),v[i].power-b,cmp);
  59.             if (preyL!=v.end() && v[preyL-v.begin()].power==v[i].power-b) preyL++;
  60.             v[i].preynum=preyR-preyL;
  61.         }
  62.     }
  63.     sort(v.begin(),v.end(),cmp4);
  64.     for (ll i = 0; i<n; i++) {
  65.         cout<<v[i].prednum<<' '<<v[i].preynum<<'\n';
  66.     }
  67. }
  68.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5 3 7
8 6 5 14 12
stdout
copy 
2 1
1 0
1 0
0 1
0 2
https://ideone.com/9XLggh
language:
C++ (gcc 8.3)
created:
5 hours 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!