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

Help me to make my segment tree faster
Автор zarif_2002, история, 4 года назад, По-английски

I learned segment tree yesterday and tried to solve these following problems
399D - Painting The Wall
61E - Enemy is weak
459D - Pashmak and Parmida's problem
My solutions just barely pass the time limit.
81038127
81106193
81148972(needed faster I/O)
How can I strengthen this segment tree so that my solution fits into time limit completely.

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

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

I think array is faster than vector when the constraint is large. Also, long long is unnecessary, using int instead of long long reduces the execution time.

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

74662995

My submission for the first problem is just 300ms.

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

From where you have learnt segment tree ?

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

    From everywhere, youtube gives theory, GFG gives some idea of code, then try questions on Codeforces.

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

    First of all, segment tree is not essential in your position. Cause it would look hard for you in the green region. I suggest learning segment tree after crossing 1500. What you need right now is to get good enough to solve implementation problems and logic building for div3 C, D and div2 C. Maybe you can learn binary search and stl. Believe me, doing segment tree are not going to be helpful right now.

    Once you are comfortable with the implementation and logic building problems, then move on for algorithms.

    And you can learn segment tree from here if you desperately want. https://www.hackerearth.com/practice/notes/segment-tree-and-lazy-propagation/

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

    The competitive programmers handbook covers it nicely: https://cses.fi/book/book.pdf

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

Your segtree is fine, just use ios_base::sync_with_stdio(false). People should stop misleading other people that arrays are faster than vectors, most of the times they are not.

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

    I prefer vectors over arrays, however I would say that multi-dimensional arrays are better than multi-dimensional vectors, for example a 2D matrix where I do operations row-wise: arrays would have a great cache locality whereas in vector since the next row is at a different location you would have cache misses for all rows (though the difference would only be apparent when you are really trying to fit your slow algo in the TL xD).

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

      "in vector since the next row is at a different location", any sources about this?

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

        Ummm.... The only way I know to make a multi-dimensional vector is to use vector<vector<T>> vec(n, vector<T>(m)), and it is obvious that here the row vectors are all constructed seperately so each of them would have a different memory location.

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

      Fair point. I agree that when we start thinking about multidimensional arrays, things start to change. However, for 1D arrays I've never seen notable difference (at least, as long as you're preallocating the vector size instead of using push_back or emplace_back).

      However, there's also an upside to this. Address sanitizer can catch out-of-bounds errors on 2D vectors, and not on matrices (feel free to correct me if this is not the case).

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        For 1D preallocated vectors, yes, I have never seen a difference. Infact, if we go by stackoverflow, there is no difference at all.

        You are right about Address Sanitizer not catching it, but UBSan (-fsanitize=undefined) does.

        → Ответить