### shreyas_24's blog

By shreyas_24, history, 3 weeks ago,

Hi, i tried to solved this problem Below is the code.

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main(){
int n,k;cin>>n>>k;
vector<ll> a(n);
cin>>a[0];
for(int i=1;i<n;i++){cin>>a[i];a[i]+=a[i-1];}
for(int i=0;i<k;i++){ll temp;cin>>temp;
ll j=0;
while(temp > a[j]){j++;}
cout<<j+1<<" ";
j==0?cout<<temp<<endl:cout<<temp-a[j-1]<<endl;
}

}


But i am getting TLE. I saw a similar approach(link to that solution) that got ac . Can anyone point out the difference between the two solutions. Also I saw the tag of binary search but i'm unable to figure out how to apply binary search on this. Can someone please discuss it.Thanks!!

• 0

 » 3 weeks ago, # |   0 Both these solutions are O(N^2). I guess that other solution could be optimized more by the compiler, so it ran in time, but still much higher than normal (about 1.5s).If you inspect your code and see where the bulk of the computing time is going, it's that loop: while(temp > a[j]){j++;} You're finding the smallest index j such that it's at least temp. I'll leave you to figure out how you can optimize that part.
•  » » 3 weeks ago, # ^ |   0 Hi thanks for the hint. I implemented binary search for finding the smallest index and the time reduced from 4000ms to 1500ms and got ac.
 » 3 weeks ago, # |   0 The different is your code run in $O(N*M)$ while AC solution run in $O(N+M)$. The different is your code find iterator $j$ every $i$, while AC solution use iterator $j$ from $i-1$ for count iterator $j$ for $i$.