fork download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. typedef long long int ll;
  5.  
  6. ll get_pos(ll a[],ll k,ll val,ll s,ll i)
  7. {
  8.   ll low=i,high=s-1,mid;
  9.   while(low<=high)
  10.   {
  11.     mid=(low+high)/2;
  12.     if(a[mid]+val==k)
  13.     {
  14.       return mid-1;
  15.     }
  16.     else if(a[mid]+val>k)
  17.     {
  18.       if(a[mid-1]+val<k&&mid-1>=i)
  19.       {
  20.         return mid-1;
  21.       }
  22.       else
  23.       {
  24.         if(mid-1<i)
  25.         {
  26.           return i-1;
  27.         }
  28.         high=mid-1;
  29.       }
  30.     }
  31.     else if(a[mid]+val<k)
  32.     {
  33.       if(a[mid+1]+val>=k)
  34.       {
  35.         return mid;
  36.       }
  37.       else
  38.       {
  39.           low=mid+1;
  40.       }
  41.     }
  42.   }
  43.     return low;
  44. }
  45.  
  46. int main()
  47. {
  48.   ll n,k,p,pos,s=0;
  49.   cin>>n>>k;
  50.   ll a[n];
  51.   for(ll i=0;i<n;i++)
  52.   {
  53.     cin>>p;
  54.     if(p<k)
  55.     {
  56.       a[s]=p;
  57.       s++;
  58.     }
  59.   }
  60.   sort(a,a+s);
  61.   for(int i=0;i<s;i++)
  62.   {
  63.     cout<<a[i]<<" ";
  64.   }
  65.   cout<<endl;
  66.   ll ans=0;
  67.   for(int i=0;i<s-1;i++)
  68.   {
  69.     ll z;
  70.     ll pos=get_pos(a,k,a[i],s,i+1);
  71.     cout<<pos<<" ";
  72.     if(pos>i)
  73.     {
  74.       ans=ans+(pos-i);
  75.     }
  76.   }
  77.   cout<<endl;
  78.   cout<<ans<<endl;
  79. }
  80.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
47849787027837 47849787027837 
0 
0
https://ideone.com/j4DG9D
language:
C++14 (gcc 8.3)
created:
6 years 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!