474 B WORMS

Marmot brings n piles of worms for the mole. The input gives the number of worms in each pile. The piles are arranged in such a way that if the 1st pile contains 5 worms, then the 6th worm will belong to the 2nd pile.

For example, if the piles are: 2 7 3 4 9

then the ranges become:

[1,2], [3,9], [10,12], [13,16], [17,25]

Here, the ranges are inclusive.

So worms from 3 to 9 belong to the 2nd pile.

Now suppose the juicy worms are:1 25 11

1.worm 1 belongs to the 1st pile, so output 1

2.worm 25 belongs to the 5th pile

3.worm 11 belongs to the 3rd pile

Approach:

So basically we need to search for which pile contains a given worm number. Looking at the constraints, it’s clear that the solution should be around O(n) or O(n log n), so binary search is probably the best option.

But after realizing binary search was needed, I got confused about what exactly to apply it on. Since we are dealing with ranges, at first I thought maybe I’d need something like hashing or mapping integers to vectors/ranges, but that would be unnecessarily expensive.

While working with the ranges, we were summing the pile sizes, and suddenly i got I could use prefix sums along with lower_bound().

So first, I build the prefix sum array of the piles 2 7 3 4 9

the prefix sums become:2 9 12 16 25

Then for each juicy worm, I use binary search with lower_bound() on the prefix sum array to find the equal or greater value for finding that worm number.

Since the result index is 1-based, we dont need to think about the index.

 #include<bits/stdc++.h>
using namespace std;
    typedef  long long     ll;
    typedef vector<long long > VLL;
#define inp(v) for(auto& i:  v) cin>>i;


  void solve();

int   main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     #ifdef LOCAL
    cerr << "Execution time: " << 1000.f * clock() / CLOCKS_PER_SEC << " ms." << nl;
    #endif
    
        solve();
    return 0;       
}

void solve() {
    ll t;
    cin >> t;
    VLL worms(t); // [1,2],[3,9],[10 , 12],[13,17],[18,26]
    VLL psum(t + 1, 0);
    inp(worms);

    for (ll i=1; i <= t; i++){
        psum[i] = psum[i - 1] + worms[i - 1];
    }


    ll m;
    cin >> m;
    
   for (ll i=0; i < m; i++){
       ll juc;
       cin >> juc;
// as we have to search ,so with this constraint binery search is the best 
       auto dex= lower_bound(psum.begin(), psum.end(), juc);
       cout << dex - psum.begin();//1 index e result   dite hobe .and presum 1 index e chilo
       cout << "\n";
   }
}

Complexity:

For psum O(n)

For binery search in m queries O(mlogn)...cuz binery search in on psum and psum size in n+1 .so O(logn) for 1 query.

so TIme complexity is O(n+mlogn)