Блог пользователя GreedyXploit

Автор GreedyXploit, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • -22
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.