Re: [閒聊] 每日LeetCode

[fxfxxxfxx (愛麗絲)]

732. My Calendar III

我好不容易用線段樹刻完了
結果只比5%的快，哭了


class MyCalendarThree {
public:
    static const int maxEd = 1000000000;

    unordered_map<uint64_t,int> maxB;
    unordered_map<uint64_t,int> add;

    MyCalendarThree() {}

    int insert(int st, int ed, int l = 0, int r = maxEd) {
        uint64_t key = ((uint64_t)l << 32) | r;

        if (st <= l && r <= ed) {
            add[key] += 1;
            return maxB[key] + add[key];
        }

        int m = (l + r) / 2;
        if (st <= m)
            maxB[key] = max(maxB[key], insert(st, ed, l    , m));
        if (ed >= m + 1)
            maxB[key] = max(maxB[key], insert(st, ed, m + 1, r));
        return maxB[key] + add[key];
    }

    int book(int st, int ed) {
        return insert(st, ed - 1);
    }
};

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1665142577.A.DFC.html
推 Rushia: 寶 你可以用陣列來刻 對ㄚ
→ Jaka: 大師
→ fxfxxxfxx: 用陣列比較難做吧 總不能開個2*10^9的陣列
→ Rushia: ㄛ 我沒看測資 那你用自己的NODE來做會比較好吧