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!!
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:
You're finding the smallest index
jsuch that it's at leasttemp. I'll leave you to figure out how you can optimize that part.