Advertisement
YEZAELP

CUBE-195: Infinity Lime

Sep 6th, 2020
130
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.05 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct node{
  6.     int num, ques, ans;
  7. };
  8.  
  9. bool sort_num(node a, node b){
  10.     return a.num < b.num;
  11. }
  12.  
  13. bool sort_ques(node a, node b){
  14.     return a.ques < b.ques;
  15. }
  16.  
  17. int main(){
  18.  
  19.     int n, k;
  20.     scanf("%d%d", &n, &k);
  21.  
  22.     int ar[n+1];
  23.     ar[0] = 0;
  24.     for(int i=1;i<=n;i++) scanf("%d", &ar[i]);
  25.  
  26.     sort(ar+1, ar+n+1);
  27.  
  28.     node Q[k+1];
  29.  
  30.     for(int i=1;i<=k;i++){
  31.         scanf("%d", &Q[i].num);
  32.         Q[i].ques = i;
  33.     }
  34.  
  35.     sort(Q+1, Q+k+1, sort_num);
  36.  
  37.     // find ans
  38.     int idx = 1, sum = 0;// idx = Q
  39.     for(int i=1;i<=n;i++){
  40.         sum += ar[i] - ar[i-1] - 1;
  41.         while(idx <= k and sum >= Q[idx].num){
  42.             Q[idx].ans = ar[i] - sum + Q[idx].num - 1;
  43.             idx ++;
  44.         }
  45.         if(idx > k) break;
  46.     }
  47.  
  48.     while(idx <= k){
  49.         Q[idx].ans = ar[n] + Q[idx].num - sum;
  50.         idx ++;
  51.     }
  52.  
  53.     sort(Q+1, Q+k+1, sort_ques);
  54.  
  55.     // print ans
  56.     for(int i=1;i<=k;i++){
  57.         printf("%d ",Q[i].ans);
  58.     }
  59.  
  60.     return 0;
  61. }
  62.  
Advertisement
RAW Paste Data Copied
Advertisement