Advertisement
Guest User

Untitled

a guest
Jan 25th, 2020
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.39 KB | None | 0 0
  1. //
  2. // Created by Adam Szokalski on 25/01/2020.
  3. //
  4.  
  5. #include<iostream>
  6. #include<algorithm>
  7. using namespace std;
  8.  
  9. int S[500000];
  10. pair<int, int> M[500000];
  11. int W[500000];
  12.  
  13. int find_first_larger(int x, int p, int k){
  14.     int i;
  15.     while(p < k){
  16.         i = (p + k) / 2;
  17.  
  18.         if      (M[i].first <= x){p=i+1;}
  19.         else if (M[i].first >  x){k=i;}
  20.  
  21.         if(M[p].first == M[k].first){
  22.             break;
  23.         }
  24.     }
  25.     return p;
  26. }
  27.  
  28. void climb(int n, int p, int k){
  29.     int i;
  30.     for (i = 0; i < n; ++i) {
  31.  
  32.         int f = find_first_larger(S[i], p, k);
  33.  
  34.         if(M[f].first <= S[i] || f > k){
  35.             break;
  36.         } else {
  37.             for (int j = p; j < f; ++j) {
  38.  
  39.                 W[M[j].second] = i;
  40.             }
  41.  
  42.             p = f;
  43.         }
  44.     }
  45.  
  46.  
  47.     for (int l = p; l <= k; ++l) {
  48.         if(M[l].first > S[n-1]){
  49.             W[M[l].second] = n;
  50.         } else{
  51.             W[M[l].second] = i;
  52.         }
  53.     }
  54. }
  55. int main(){
  56.     ios_base::sync_with_stdio(0);
  57.     cout.tie(0);
  58.     cin.tie(0);
  59.  
  60.     int n, m;
  61.     cin>> n >> m;
  62.  
  63.     for (int i = 0; i < n; ++i) {
  64.         cin>> S[i];
  65.     }
  66.  
  67.     for (int j = 0; j < m; ++j) {
  68.         cin>> M[j].first;
  69.         M[j].second = j;
  70.     }
  71.  
  72.     sort(M, M+m);
  73.     climb(n, 0, m-1);
  74.  
  75.     for (int k = 0; k < m; ++k) {
  76.         cout<< W[k] << " ";
  77.     }
  78.     cout<<"\n";
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement