제출 #713545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
713545		four_specks	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	39 ms	3036 KiB

apple

#include <bits/stdc++.h>

using namespace std;

namespace
{
    struct SegTree
    {
        SegTree() {}
        SegTree(long _l, long _r) : l(_l), r(_r), val(0), lz(0) {}

        long l, r;
        long val;
        bool lz;

        unique_ptr<SegTree> lc, rc;

        void pull()
        {
            val = 0;
            if (lc)
                val += lc->val;
            if (rc)
                val += rc->val;
        }

        void update(long pl, long pr)
        {
            if (r <= pl || pr <= l)
                return;

            if (lz)
                return;

            if (pl <= l && r <= pr)
            {
                lz = 1;
                val = r - l;
                return;
            }

            long mid = (l + r) / 2;

            if (!lc)
                lc = make_unique<SegTree>(l, mid);
            lc->update(pl, pr);

            if (!rc)
                rc = make_unique<SegTree>(mid, r);
            rc->update(pl, pr);

            pull();
        }

        long query(long pl, long pr)
        {
            if (r <= pl || pr <= l)
                return 0;

            if (pl <= l && r <= pr)
                return val;

            if (lz)
                return min(r, pr) - max(l, pl);

            long ret = 0;
            if (lc)
                ret += lc->query(pl, pr);
            if (rc)
                ret += rc->query(pl, pr);

            return ret;
        }
    };

} // namespace

void solve()
{
    int m;
    cin >> m;

    long c = 0;
    SegTree st(1, 1'000'000'001);
    for (int i = 0; i < m; i++)
    {
        int t;
        long l, r;
        cin >> t >> l >> r;

        l += c;
        r += c;

        if (t == 1)
        {
            c = st.query(l, r + 1);

            cout << c << '\n';
        }
        else if (t == 2)
            st.update(l, r + 1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

• Subtask 1: 100 / 100