Editorial- ATBIN

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author: Adarsh Kumar Sinha

DIFFICULTY:

EASY

PREREQUISITES:

Map, Binary Search, Prexif Sum.

EXPLANATION:

Solution 1:

Make an array ( pre[] ) of prefix sum for the queue of people starting from the left.
Use Binary Search over the pre array for each query of theaters. If found, print “YES”, else “NO”.

Solution for subtask 1 
     #include<bits/stdc++.h>
    
    #define ll long long
    
    #define endl '\n'
    
    #define elif else if
    
    #define pb push_back
    
    
    using namespace std;
    
    
    int t;
    
    int main(){
    
    ios_base::sync_with_stdio(false);
    
    cin.tie(NULL);
    
    int n;
    
    cin >> n;
    
    int ar[n],q[n];
    
    for(int i=0; i<n; i++){
    
    cin >> ar[i];
    
    }
    
    for(int i=0; i<n; i++){
    
    cin >> q[i];
    
    }
    
    vector<int> pre(n+1);
    
    pre[0]=0;
    
    for(int i=0; i<n; i++){
    
    pre[i+1]=pre[i]+ar[i];
    
    }
    
    for(int i=0; i<n; i++){
    
    auto it = lower_bound(pre.begin(),pre.end(),q[i]);
    
    if(it!=pre.end() && *it==q[i]){
    
    cout << "YES" << endl;
    
    }
    
    else{
    
    cout << "NO" << endl;

}

}

}

Solution 2 (Simpler):

Instead of doing a binary search, all possible prefix sums can be stored in a map/ unordered_map. During each query just see if this there is key present in the map for the particular query. If found, print “YES”, else “NO”.

1 Like