Advertisement
tepyotin2

divideandsummarize

Jun 20th, 2025
303
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.54 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. struct Value{
  8.     ll val;
  9.     int pos;
  10.     bool operator<(const Value &a) const{
  11.         return val<a.val;
  12.     }
  13. };
  14.  
  15. int t;
  16. set<ll> sum;
  17. int n, q;
  18. vector<ll> pfs;
  19.  
  20. void Slice(vector<Value> arr){
  21.     //slicing works by dividing the array into left and right based on the mid
  22.     //which is min + max values of the array divided by 2
  23.     Value mid;
  24.     ll add = arr[0].val+arr[arr.size()-1].val;
  25.     if(add%2 == 0){
  26.         mid.val = add/2;
  27.     }else{
  28.         mid.val = (add-1)/2;
  29.     }
  30.     //cout << "mid value: " << mid.val << '\n';
  31.     //auto it = upper_bound(arr.begin(), arr.end(), mid,
  32.     //[](ll v, const Value& check){
  33.         //return v<check.val;
  34.     //});
  35.     auto it = upper_bound(arr.begin(), arr.end(), mid);
  36.     it--;
  37.     //Value res = *it;
  38.     //cout << res.val << ", " << res.pos << '\n';
  39.     int idx = distance(arr.begin(), it);
  40.     //cout << idx << '\n';
  41.     vector<Value> left;
  42.     left.assign(arr.begin()+0, arr.begin()+idx+1);
  43.     vector<Value> right;
  44.     right.assign(arr.begin()+idx+1, arr.begin()+arr.size());
  45.     if(!left.empty() && left.size()!=arr.size()){
  46.         sum.insert(pfs[left[left.size()-1].pos]-(pfs[left[0].pos-1]));
  47.         Slice(left);
  48.     }
  49.     if(!right.empty() && right.size()!=arr.size()){
  50.         sum.insert(pfs[right[right.size()-1].pos]-(pfs[right[0].pos-1]));
  51.         Slice(right);
  52.     }
  53.     //cout << "left: ";
  54.     //for(int i=0; i<left.size(); i++){
  55.         //cout << left[i].val << " ";
  56.     //}
  57.     //cout << '\n';
  58.     //cout << "right: ";
  59.     //for(int i=0; i<right.size(); i++){
  60.         //cout << right[i].val << " ";
  61.     //}
  62.     //cout << '\n';
  63. }
  64.  
  65. int main(){
  66.     //freopen("divideandsummarize.in", "r", stdin);
  67.    
  68.     cin >> t;
  69.     while(t--){
  70.         //get the array, sort, then send to slicing function and then get sums
  71.         //which can be used to check if each querry is valid and need to use
  72.         //set as the data structure for sums to prevent time limit exceeded
  73.         cin >> n >> q;
  74.         sum.clear();
  75.         vector<Value> arr;
  76.         pfs.resize(n+1, 0);
  77.         ll v;
  78.         ll sum1 = 0;
  79.         for(int i=0; i<n; i++){
  80.             cin >> v;
  81.             sum1+=v;
  82.             arr.push_back({v, 0});
  83.         }
  84.         sum.insert(sum1);
  85.         sort(arr.begin(), arr.end());
  86.         sum1 = 0;
  87.         for(int i=0; i<n; i++){
  88.             sum1+=arr[i].val;
  89.             arr[i].pos = i+1;
  90.             pfs[i+1] = sum1;
  91.             //cout << "val: " << arr[i].val << ", pos: " << arr[i].pos << ", pfs: " << pfs[i+1] << '\n';
  92.         }
  93.         Slice(arr);
  94.         ll val;
  95.         for(int i=0; i<q; i++){
  96.             cin >> val;
  97.             //auto it = find(sum.begin(), sum.end(), val);
  98.             auto it = sum.find(val);
  99.             if(it!=sum.end()){
  100.                 cout << "Yes" << '\n';
  101.             }else{
  102.                 cout << "No" << '\n';
  103.             }
  104.         }
  105.     }
  106.    
  107.     return 0;
  108. }
  109.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement