Submission #1219140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219140		iamhereforfun	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	388 ms	260740 KiB

apple

// IamHereForFun //

#include <bits/stdc++.h>

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 16;
const int M = 1355;
const int C = 26;
const int LG = 61;
const int R = 25e3 + 5;
const int B = 450;
const int O = 3e5 + 5;
const int INF = 1e9 + 5;
const int MOD = 998244353;
const int nx[] = {0, 1, 0, -1}, ny[] = {1, 0, -1, 0};

struct SparseSegmentTree
{
    struct Node
    {
        Node *le, *ri;
        int lazy, val;
        Node()
        {
            le = ri = NULL;
            lazy = val = 0;
        }
    };
    Node *root;
    int n;
    SparseSegmentTree(int len)
    {
        root = new Node();
        n = len;
    }
    void apply(Node *a, Node *b, int len)
    {
        if (b->lazy == 1)
        {
            a->lazy = 1;
        }
    }
    void prop(Node *cur, int l, int r)
    {
        if (cur->lazy == 1)
            cur->val = r - l + 1;
        if (l != r)
        {
            if (cur->le == NULL)
                cur->le = new Node();
            if (cur->ri == NULL)
                cur->ri = new Node();
            int m = (l + r) / 2;
            apply(cur->le, cur, m - l + 1);
            apply(cur->ri, cur, r - (m + 1) + 1);
        }
    }
    void update(Node *cur, int l, int r, int tl, int tr)
    {
        prop(cur, l, r);
        if (tl > tr)
            return;
        if (tl <= l && r <= tr)
        {
            // cout << l << " " << r << "u\n";
            cur->lazy = 1;
            prop(cur, l, r);
        }
        else
        {
            int m = (l + r) / 2;
            update(cur->le, l, m, tl, min(tr, m));
            update(cur->ri, m + 1, r, max(tl, m + 1), tr);
            cur->val = cur->le->val + cur->ri->val;
        }
    }
    int get(Node *cur, int l, int r, int tl, int tr)
    {
        prop(cur, l, r);
        if (tl > tr)
            return 0;
        if (tl <= l && r <= tr)
        {
            // cout << l << " " << r << " " << cur->val << " " << tl << " " << tr << "\n";
            return cur->val;
        }
        else
        {
            int m = (l + r) / 2;
            return get(cur->le, l, m, tl, min(tr, m)) +
                   get(cur->ri, m + 1, r, max(tl, m + 1), tr);
        }
    }
    void update(int l, int r)
    {
        update(root, 0, n - 1, l, r);
    }
    int get(int l, int r)
    {
        return get(root, 0, n - 1, l, r);
    }
};

int q, last = 0;

void solve()
{
    cin >> q;
    SparseSegmentTree st(1e9 + 1e8);
    for (int x = 0; x < q; x++)
    {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1)
        {
            int i = st.get(l + last, r + last);
            cout << i << "\n";
            last = i;
        }
        else
        {
            st.update(l + last, r + last);
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

• Subtask 1: 100 / 100