답안 #713545

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
713545 2023-03-22T12:46:57 Z four_specks 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
39 ms 3036 KB
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 5 ms 464 KB Output is correct
8 Correct 19 ms 1364 KB Output is correct
9 Correct 36 ms 2364 KB Output is correct
10 Correct 36 ms 2508 KB Output is correct
11 Correct 35 ms 2492 KB Output is correct
12 Correct 36 ms 2388 KB Output is correct
13 Correct 39 ms 2764 KB Output is correct
14 Correct 39 ms 2816 KB Output is correct
15 Correct 34 ms 3004 KB Output is correct
16 Correct 36 ms 3036 KB Output is correct
17 Correct 31 ms 2848 KB Output is correct
18 Correct 30 ms 2892 KB Output is correct
19 Correct 33 ms 2944 KB Output is correct
20 Correct 34 ms 3016 KB Output is correct