GreedyXploit's blog

By GreedyXploit, history, 6 weeks ago, In English

QUESTION LINK

    #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

 
 
 
 
  • Vote: I like it
  • -22
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

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 vector c of that length?

Also: study how time complexity works. It is an incredibly powerful tool and avoids 98% of TLEs and MLEs.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    thanks bro for your solution

    Can you explain how do i solve it with my logic ?? plssss

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    pls suggest any good resource for understanding time complexities

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +12 Vote: I do not like it
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it -26 Vote: I do not like it

        thanks bro

        bro PLs can you be my mentor for compitetive programming i really need one i want to qualify IOI olympiad pls help me to show direction

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.