Submission #713545

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
713545	2023-03-22T12:46:57 Z	four_specks	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	39 ms	3036 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	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