1. C++ / Говнокод #17928

    +56

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    std::map<int, int> aSummator; //Массив частичных сумм
    std::vector<int> v; //Исходный массив
    
    void InitSummator()
    {
        aSummator[0] = v[0];
        aSummator[-1] = 0;
    
        for(int i = 1; i < int(v.size()); i++)
        {
            aSummator[i] = aSummator[i - 1] + v[i];
        }
    }
    
    int GetSum(int l, int r)
    {
        return aSummator[r] - aSummator[l - 1]; 
    }

    Как я писал сумматор 0.1 года назад. Вместо того, чтобы написать один if, я использовал std::map, что увеличило ассимптотику алгоритма на запрос с O(1) до O(log(n)). Но задачу при тех ограничениях (в массиве до 100000 элементов, запросов не более 100000) алгоритм решил. Преподу, естественно, показывать забоялся.

    Запостил: Janycz, 03 Апреля 2015

    Комментарии (18) RSS

    • >0.1 года назад.
      36,525 дней?
      Ответить
      • Это при условии, что автор пользуется юлианским календарём.
        Ответить
    • std::partial_sum

      > Вместо того, чтобы написать один if
      Где здесь нужен if ?
      Ответить
      • std::partial_sum работает за линейное время. Слишком медленно.
        Ответить
      • > Где здесь нужен if ?
        Понял, в GetSum, чтобы обрабатывать запрос на нулевой индекс.
        Если массив частичных сумм сместить на один индекс, как у тебя примерно и сделано, то никаких ифов не надо.
        sums[r + 1] - sums[l].
        Ответить
    • Говно в том, что aSummator[0] можно было не инициализировать. А цикл можно было писать с нуля. Да?
      Ответить

    Добавить комментарий