Can inserting 5*1e8 element in long long multiset crash the program?

Question

I seem to have run in a weird problem. I have a multiset consisting of long longs, but when I try to insert number 5*1e8, it crashes. For more info, when I try to insert the number the multiset is empty ( but I don't see how that could affect anything ). the code is down below.

I added some string outputs, to pinpoint where the program crashes. This is a solution to problem 1418D on codeforces ( https://codeforces.com/contest/1418/problem/D ) and my program crashes on the second testcase. the program stops when it hits insert which comes after lfdsa string and iterators, multiset size is outputed.

Any help is appreciated and sorry for my bad english.

The test case is :

5 8
5 1 2 4 3
0 1
0 2
0 3
0 4
0 5
1 1000000000
1 1
1 500000000

Code

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int main()
{
    multiset<ll> dif,arr;
    ll n,q;
    cin>>n>>q;
    ll x[n+1];
    for(ll k=1;k<=n;k++)
    {
        cin>>x[k];
        arr.insert(x[k]);
    }
    sort(x+1,x+1+n);
    for(ll k=2;k<=n;k++)
    {
        dif.insert(x[k]-x[k-1]);
    }
    multiset<ll>::iterator st,nd,LargestDif,it;
    
    st=arr.begin();
    nd=arr.end();
    LargestDif=dif.end();
    if(n!=1) LargestDif--;
    nd--;
    if(n>2) cout<<*nd-*st-*LargestDif<<endl;
    else cout<<"0"<<endl;
    
    for(ll k=1;k<=q;k++)
    {
        ll type,cord;
        cin>>type>>cord;
        if(arr.size()<3 && type==0)
        {
            cout<<0<<endl;
            arr.erase(arr.find(cord));
            continue;
        }
        if(arr.size()<2 && type==1)
        {
            cout<<0<<endl;
            arr.insert(cord);
            continue;
        }
        cout<<"jfads"<<endl;
        if(type==1)
        {
            arr.insert(cord);
            it=arr.find(cord);
            multiset<ll>::iterator it1,it2;
            it1=it;
            it2=it;
            it2++;
            cout<<"ghfd"<<endl;
            if(it==arr.begin())
            {
                dif.insert(*it2-*it);
            }
            else
            {
                cout<<"lfds"<<endl;
                it1--;
                if(it2==arr.end())
                {
                    cout<<"klfds"<<endl;
                    dif.insert(*it-*it1);
                }
                else
                {
                    cout<<"lfdsa"<<endl;
                    dif.erase(dif.find(*it2-*it1));
                    cout<<*it<<" "<<*it2<<" "<<*it2-*it<<" "<<dif.size()<<endl;
                    ll o=*it2-*it;
                    dif.insert(o);
                    cout<<"qwere"<<endl;
                    dif.insert(*it-*it1);
                }
                cout<<";fdasd"<<endl;
            }
        }
        else
        {
            it=arr.find(cord);
            multiset<ll>::iterator it1,it2;
            it1=it;
            it2=it;
            it2++;
            if(it==arr.begin())
            {
                dif.erase(dif.find(*it2-*it));  
            }
            else
            {
                it1--;
                if(it2==arr.end())
                {
                    dif.erase(dif.find(*it-*it1));  
                }
                else
                {
                    dif.erase(dif.find(*it2-*it));
                    dif.erase(dif.find(*it-*it1));
                    dif.insert(*it2-*it1);
                }
            }
            cout<<"sanlfas"<<endl;
            arr.erase(arr.find(cord));
        }
        cout<<"dsafdsf"<<endl;
        st=arr.begin();
        nd=arr.end();
        cout<<"bcd"<<endl;
        nd--;
        cout<<"ghsfd "<<dif.size()<<endl;
        LargestDif=dif.end();
        LargestDif--;
        cout<<"oj;dfas"<<endl;
        cout<<*nd-*st-*LargestDif<<endl;
    }
}

_`#include #define ll long long #define pb push_back using namespace std;`_ Please, please, please stop doing that shite!!!! — πάντα ῥεῖ, Jun 01 '22 at 15:11
`ll x[n+1];` is a [variable-length array](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard) which is not actually part of the C++ standard. — Nathan Pierson, Jun 01 '22 at 15:12
Your code is unreadable with all those `#define`s. Also, `ll x[n+1];` will cause the stack to overflow for large `n`, and it is not valid C++ in the first place, so PLEASE stop writing code in this fashion. — ChrisMM, Jun 01 '22 at 15:13
Does it help you code _correctly_ faster? It makes it harder for anyone else to figure out what's going on and offer suggestions. — Nathan Pierson, Jun 01 '22 at 15:13
@ChrisMM ok, I will change it and post the results in comments — giorgigiorgi, Jun 01 '22 at 15:13
Main problem here is `main`. Whole code is hiding in `main`. Learn to split code into small function which do single thing ASAP! — Marek R, Jun 01 '22 at 15:13
@giorgigiorgi https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h , https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice to start with... — πάντα ῥεῖ, Jun 01 '22 at 15:14
changing the x[n+1] to x[100001] doesn't do anything, also the test case that my code fails in has a small n and x array is almost never used @ChrisMM — giorgigiorgi, Jun 01 '22 at 15:15
Do you have enough RAM for the allocated memory? (I'm guessing about 50 GB. But I could be off by a factor of 4, in either direction.) — Eljay, Jun 01 '22 at 15:15
@NathanPierson I've always struggled with developing a good style, I'm sorry for inconvenience — giorgigiorgi, Jun 01 '22 at 15:16
With so many things, we haven't even gotten to the fact that this question should be edited to include a [minimal, reproducible example](https://stackoverflow.com/help/minimal-reproducible-example), emphasis on minimal. That will cut down on the number of suggestions to fix problems or legibility issues that don't actually address your problem. — Nathan Pierson, Jun 01 '22 at 15:17
What the above links skip is the effect they have in competitions where writing code quickly is important. Unless you have precompiled headers set up correctly, when `#include` includes the entire C++ Standard library, the entire C++ Standard library needs to be compiled each and every time, making every build take around ten times as long. Usually by the third compile, you've lost all of the time you saved over typing in the correct headers. — user4581301, Jun 01 '22 at 15:19
@NathanPierson added the test case in the question too, you can also see it in the link provided. — giorgigiorgi, Jun 01 '22 at 15:20
@user4581301 That's really helpful and good to know, while writing contests I have a code prepared that I edit, so I'll change the bits/stdc++.h to some libraries I always use and add some if I need them. — giorgigiorgi, Jun 01 '22 at 15:22
@user4581301 _"... in competitions where writing code quickly is important ..."_ important **quickly** how? 1st to answer, less characters to compile?? Is that relevant for SO coding questions, or just bad practice, and cargo cult programming? — πάντα ῥεῖ, Jun 01 '22 at 15:30
Side note: Don't learn C++ by by reading and writing competition code. That's not what competitions are for. They can be fun and good practice once you know the language, but competitions mostly teach math and and algorithm tricks and bad programming habits. When learning the language, you need clear, expressive and robust examples. Competition code is written quickly with minimal effort with a goal of running once very quickly under ideal circumstances. Real programs need to be maintained and run properly and consistently for years and correctly handle usage that can be downright toxic. — user4581301, Jun 01 '22 at 15:32
@user4581301 well, I myself am a competitive programmer, well that's probably why my codes turn out ugly. — giorgigiorgi, Jun 01 '22 at 15:37
@πάνταῥεῖ in online contests and programming competitions, quickly writing small codes can be crucial. — giorgigiorgi, Jun 01 '22 at 15:39
@πάνταῥεῖ you know it, I know it. The goals of code submitted to competitions is orthogonal to code for an engineered product. A competition is usually scored by the time it took to solve all of the problems or the number of problems solved if no one solved all of the problems. Ties are broken by faster solutions. At no point does proper engineering, style or common sense enter the equation. If the program fails utterly with slightly different inputs or will murder your mother if its run twice, that's fine. Fast is the ONLY thing that matters. — user4581301, Jun 01 '22 at 15:41
@giorgigiorgi when asking a question on stack overflow, don't provide ugly code. 1) most people are going to take one look at it and move on to another question. They won't spend any time trying to untangle it. This is because a confusing mess of crap won't be very helpful to future programmers with a similar problem because they won't be able to recognize it's a similar problem. 2) When debugging the first thing you do is remove all common error-causing agents. Then you attempt to isolate the bug. Dump raw competition code and it's obvious you've done neither. — user4581301, Jun 01 '22 at 15:50
Code golf wouldn't take it either. They might take the problem, but they wouldn't play Whack-A-Mole with the code. — user4581301, Jun 01 '22 at 15:52
Here is your code with the correct headers (because otherwise it's murderous on Matt Godbolt's servers) and nothing else changed. I've used the default input `-O2` (usually the setting I see in competitions) and turned on a couple sanitizers. The sanitizer diagnostics should be helpful. Consider turning off the optimizer if you need more detail, but know that doing so may change the error subtly. https://godbolt.org/z/eMYjGd8zr — user4581301, Jun 01 '22 at 16:00

Marek R · Answer 1 · 2022-06-07T10:53:18.977

1

Not on the main topic, but to big for a comment.

Just to clean up this mess:

#include<bits/stdc++.h>
Macros are harmful. They do not respect namespaces are processed in different stage then compilation. Error caused by them are hard to understand and fix. And some of macros you have used can be replaced nicely:

// #define ll long long
using ll = long long;

#define pb push_back is very bad - makes code harder to read. Just drop it.
using namespace std;
any function which is long is hard to read understudy, correct and test. You used only main with everything in it. Learn to use small function which does only one thing ASAP.

edited Jun 07 '22 at 10:53

answered Jun 01 '22 at 15:22

Marek R

32,568
6
55
140

using ll = long long returns a compilation, would using typedef be fine? – giorgigiorgi Jun 01 '22 at 15:25
`typedef` and `using` are equivalent in practice. `using` is easier to read. Main difference is that `typedef` works in `C`. – Marek R Jun 01 '22 at 15:28
2

In this case, `typedef` and `using` do the same thing with different syntax. The problem with `#define` is it's simple text substitution. Wherever the preprocessor finds the token `ll`, it will be replaced with `long long` not matter how stupid doing it would be. This results in nigh-inscrutable errors later in the build process when the compiler tries to interpret it and fails. – user4581301 Jun 01 '22 at 15:29

Can inserting 5*1e8 element in long long multiset crash the program?

1 Answers1