aijey's blog

Can't compile file: Compilation process timed out.
By aijey, history, 5 years ago, In English

Hi guys. I wrote my segment tree structure using static buffer in order not to use heap memory. Locally my code was compiling OK, but at Codeforces it wasn't. I'd be grateful if somebody could explain me what's the problem.

Here are links of my submissions. In first submission I had overloaded new operator for my segment tree structure. In second submission I've written my own function, which returns void*. Both submission I tried on all available GNU compilers, and any of them wasn't compiling. Third submission was sent using Microsoft C++ 2017 and it compiled fine.

P.S. I know that I could have written segment tree using arrays instead of pointers, but it's too easy and boring :D

  • Vote: I like it
  • +23
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

It's likely a compiler issue, and the easiest fix is to initialize member variables in the default constructor and not using default initializers, something like this:

//...
pair<int, int> val;
segmentTree* left;
segmentTree* right;
int tl, tr;

segmentTree() : val(0, 0), left(nullptr), right(nullptr), tl(0), tr(1ll<<20) {}
//...
→ Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

You can take a look at this blog and this blog about similar issue.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

I believe GCC sees segmentTree as POD (plain old data) structure and tries to pre-initialize your 5M array and write it into the binary. Takes long time and lot of memory.

You can work around by adding empty constructor: 63382691. I believe GCC will then initialize the array in run time.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It's a static member. All static class members are Plain Old Data, the difference is that when there's no explicit initialisation, it goes to the .bss section in binary instead of the usual .data section, and .bss is stored as just the size in bytes since it's automatically initialised to $$$0$$$ by the OS when loading the executable.

    → Reply