Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- struct Value{
- ll val;
- int pos;
- bool operator<(const Value &a) const{
- return val<a.val;
- }
- };
- int t;
- set<ll> sum;
- int n, q;
- vector<ll> pfs;
- void Slice(vector<Value> arr){
- //slicing works by dividing the array into left and right based on the mid
- //which is min + max values of the array divided by 2
- Value mid;
- ll add = arr[0].val+arr[arr.size()-1].val;
- if(add%2 == 0){
- mid.val = add/2;
- }else{
- mid.val = (add-1)/2;
- }
- //cout << "mid value: " << mid.val << '\n';
- //auto it = upper_bound(arr.begin(), arr.end(), mid,
- //[](ll v, const Value& check){
- //return v<check.val;
- //});
- auto it = upper_bound(arr.begin(), arr.end(), mid);
- it--;
- //Value res = *it;
- //cout << res.val << ", " << res.pos << '\n';
- int idx = distance(arr.begin(), it);
- //cout << idx << '\n';
- vector<Value> left;
- left.assign(arr.begin()+0, arr.begin()+idx+1);
- vector<Value> right;
- right.assign(arr.begin()+idx+1, arr.begin()+arr.size());
- if(!left.empty() && left.size()!=arr.size()){
- sum.insert(pfs[left[left.size()-1].pos]-(pfs[left[0].pos-1]));
- Slice(left);
- }
- if(!right.empty() && right.size()!=arr.size()){
- sum.insert(pfs[right[right.size()-1].pos]-(pfs[right[0].pos-1]));
- Slice(right);
- }
- //cout << "left: ";
- //for(int i=0; i<left.size(); i++){
- //cout << left[i].val << " ";
- //}
- //cout << '\n';
- //cout << "right: ";
- //for(int i=0; i<right.size(); i++){
- //cout << right[i].val << " ";
- //}
- //cout << '\n';
- }
- int main(){
- //freopen("divideandsummarize.in", "r", stdin);
- cin >> t;
- while(t--){
- //get the array, sort, then send to slicing function and then get sums
- //which can be used to check if each querry is valid and need to use
- //set as the data structure for sums to prevent time limit exceeded
- cin >> n >> q;
- sum.clear();
- vector<Value> arr;
- pfs.resize(n+1, 0);
- ll v;
- ll sum1 = 0;
- for(int i=0; i<n; i++){
- cin >> v;
- sum1+=v;
- arr.push_back({v, 0});
- }
- sum.insert(sum1);
- sort(arr.begin(), arr.end());
- sum1 = 0;
- for(int i=0; i<n; i++){
- sum1+=arr[i].val;
- arr[i].pos = i+1;
- pfs[i+1] = sum1;
- //cout << "val: " << arr[i].val << ", pos: " << arr[i].pos << ", pfs: " << pfs[i+1] << '\n';
- }
- Slice(arr);
- ll val;
- for(int i=0; i<q; i++){
- cin >> val;
- //auto it = find(sum.begin(), sum.end(), val);
- auto it = sum.find(val);
- if(it!=sum.end()){
- cout << "Yes" << '\n';
- }else{
- cout << "No" << '\n';
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement