Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2020
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.30 KB | None | 0 0
  1. //
  2. // Created by Adam Szokalski on 23/01/2020.
  3. //
  4.  
  5. #include<iostream>
  6. #include<algorithm>
  7.  
  8. using namespace std;
  9.  
  10. long long T[1000000];
  11. int O[100000];
  12.  
  13. int count(long long x, int n){
  14.  
  15.     int p = 0;
  16.     int k = n;
  17.     int i = 0;
  18.     int old_i = -1;
  19.     while(i != old_i && p <= k){
  20.  
  21.         old_i = i;
  22.         i = p + (k-p)/2;
  23.         if(T[i] < x){
  24.  
  25.             p = i + 1;
  26.         } else if(T[i] > x){
  27.  
  28.             k = i - 1;
  29.  
  30.         } else{
  31.  
  32.             k = i;
  33.         }
  34.     }
  35.  
  36.     int first = i;
  37.  
  38.     if(T[first] != x){
  39.         return 0;
  40.     }
  41.     p = 0;
  42.     k = n;
  43.     i = 0;
  44.     old_i = -1;
  45.     while(i != old_i && p <= k){
  46.  
  47.         old_i = i;
  48.         i = p + (k-p+1)/2;
  49.  
  50.         if(T[i] < x){
  51.  
  52.             p = i + 1;
  53.  
  54.         } else if(T[i] > x){
  55.  
  56.             k = i - 1;
  57.  
  58.         } else{
  59.  
  60.             p = i;
  61.         }
  62.     }
  63.  
  64.     int last = i;
  65.  
  66.     return last-first + 1;
  67. }
  68.  
  69. int main(){
  70.     int n;
  71.     cin >> n;
  72.     for (int i = 0; i < n; ++i) {
  73.         cin >> T[i];
  74.     }
  75.  
  76.     sort(T, T + n);
  77.  
  78.     int q;
  79.     cin >> q;
  80.     for (int j = 0; j < q; ++j) {
  81.         long long question;
  82.         cin >> question;
  83.  
  84.         O[j] = count(question, n-1);
  85.     }
  86.  
  87.     for (int k = 0; k < q; ++k) {
  88.         cout << O[k] << "\n";
  89.     }
  90.     return 0;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement