Infernale

Ultimate Dragon

Jan 11th, 2019
403
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.63 KB | None | 0 0
  1. #include <stdio.h>
  2.  
  3. void merge(int arr[], int l, int m, int r){
  4.     int i, j, k;
  5.     int n1 = m - l + 1;
  6.     int n2 =  r - m;
  7.     int L[n1], R[n2];
  8.     for (i = 0; i < n1; i++)
  9.         L[i] = arr[l + i];
  10.     for (j = 0; j < n2; j++)
  11.         R[j] = arr[m + 1+ j];
  12.     i = 0;
  13.     j = 0;
  14.     k = l;
  15.     while (i < n1 && j < n2){
  16.         if (L[i] <= R[j]){
  17.             arr[k] = L[i];
  18.             i++;
  19.         }else{
  20.             arr[k] = R[j];
  21.             j++;
  22.         }
  23.         k++;
  24.     }
  25.     while (i < n1){
  26.         arr[k] = L[i];
  27.         i++;
  28.         k++;
  29.     }
  30.     while (j < n2){
  31.         arr[k] = R[j];
  32.         j++;
  33.         k++;
  34.     }
  35. }
  36. void mergeSort(int arr[], int l, int r){
  37.     if (l < r){
  38.         int m = l+(r-l)/2;
  39.         mergeSort(arr, l, m);
  40.         mergeSort(arr, m+1, r);
  41.         merge(arr, l, m, r);
  42.     }
  43. }
  44.  
  45. int count(int arr[], int n, int key){
  46.     int left = 0, right = n;
  47.     int mid;
  48.     while (left < right){
  49.         mid = left + (right-left)/2;
  50.  
  51.         if (arr[mid] == key){
  52.             while (arr[mid+1] == key && mid+1<n)
  53.                  mid++;
  54.             break;
  55.         }
  56.         else if (arr[mid] > key)
  57.             right = mid;
  58.         else
  59.             left = mid + 1;
  60.     }
  61.     while (arr[mid] > key)
  62.         mid--;
  63.     return mid + 1;
  64. }
  65.  
  66. int main(){
  67.     int size, queries, temp;
  68.     scanf("%d %d", &size, &queries);
  69.     int data[size];
  70.     for(int i=0;i<size;i++){
  71.         scanf("%d", &data[i]);
  72.     }
  73.     mergeSort(data, 0, size-1);
  74.     while(queries--){
  75.         scanf("%d", &temp);
  76.         printf("%d\n", count(data, size, temp));
  77.     }
  78.     return 0;
  79. }
Add Comment
Please, Sign In to add comment