#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
long long n ; //floors
long long m ; //letters
cin>>n;
cin>>m;
long long total = 0;
vector<long long >a;
for(long long i = 0 ; i<n;i++)
{
long long k;
cin>>k;
total += k;
a.push_back(total);
}
//cin>>m;
vector<long long>b;
for(int i = 0 ; i<m;i++)
{
long long k ;
cin>>k;
b.push_back(k);
}
for(long long i = 0 ; i<m ; i++)
{
long long letter = b[i];
auto f = lower_bound(a.begin() , a.end() , letter) - a.begin();
vector<long long>c;
long long j = (f == 0)?1:a[f-1];
while(j<=a[f])
{
c.push_back(j);
++j;
}
auto r = lower_bound(c.begin() , c.end() , letter) - c.begin();
if(letter<=10)
cout<<f+1<<" "<<r+1<<"\n";
else
cout<<f+1<<" "<<r<<"\n";
}
}
THIS IS MY code but it is having MEMORY LIMIT EXCEEDED
pls guys give a detailed solution code.And also say what is wrong in my code
It gets MLE because you use too much memory.
a[1]
from your code can already be up to $$$10^{10}$$$, and then you make a vectorc
of that length?Also: study how time complexity works. It is an incredibly powerful tool and avoids 98% of TLEs and MLEs.
pls suggest any good resource for understanding time complexities
here
Here's my submission: 93175307
I basically did prefix sums on the first array and then used binary search to find the element in the array. Once I did that, if binary search returned the first element of the array I just printed the number of letters given in that query otherwise I subtracted a[i-1] from the given number of letters.
You should definitely check out the editorial, it's easy to understand.