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

Can't compile file: Compilation process timed out.
Автор aijey, история, 5 лет назад, По-английски

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

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

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

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) {}
//...
→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить