fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. int main()
  6. {
  7.     long long int t,n,q,i,count,j,k,w,index,v;
  8.     //cin>>t;
  9.     scanf("%lld",&t);
  10.     while(t--)
  11.     {
  12.         //cin>>n>>q;
  13.         scanf("%lld %lld",&n,&q);
  14.         vector<long long int> a(n),b(n);
  15.         for(i=0;i<n;i++)
  16.             scanf("%lld",&a[i]);//cin>>a[i];
  17.         sort(a.begin(),a.end());
  18.         //Sorting to reduce work
  19.         b=a;
  20.         reverse(b.begin(),b.end());
  21.         //reversing because it is easier imagining to skip some elements in the start
  22.         w=n; //a backup because i will modify 'n'
  23.         for(i=0;i<q;i++)
  24.         {
  25.             n=w; //re-storing value of 'n' before ever query
  26.             count=0;//initialising count
  27.             cin>>k;
  28.             index=n-((lower_bound(a.begin(),a.end(),k))-a.begin()); 
  29.             /*
  30.             finding the first value that is not less than k
  31.             i.e if array 'a' which is in increasing order is 1 2 2 5
  32.             k=5 will return 3
  33.             k=2 will return 1
  34.             k=3 will return 2
  35.             
  36.             Then index of next smaller value is calculated for array b using n-lower_bound
  37.             */
  38.                 count+=(index);//adding the number of values greater than k
  39.             for(j=index;j<n ;j++)
  40.             {
  41.                 v=k-b[j];//calculating the difference
  42.                     if(v<=n-j-1)//checking if that number of elements are available
  43.                 {
  44.                         //cout<<"\nhere \n";
  45.                     n=n-(v);//if available , they are removed from array(reducing n we won't access them)
  46.                     count++;
  47.                 }
  48.                 else
  49.                 	break;
  50.  
  51.             }
  52.             printf("%lld\n",count);//cout<<count<<"\n";
  53.         }
  54.  
  55.  
  56.     }
  57. }
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
2
5 11
21 9 5 8 10
26
22
21
15
10
9
8
7
6
5
0
5 6
1 2 4 4 5
0
1
2
3
4
5
stdout
copy 
0
1
1
1
3
4
4
4
4
5
5
5
5
4
4
3
3
https://ideone.com/zxhj2H
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!