Submission #1276332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276332		ayaz	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	131 ms	300864 KiB

apple

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>

const int MXN = 2e5+5;
const ll mod = 1e9+7;

struct SegTree {
    struct node {
        int li=0, ri=0, lz=0;
        ll res=0;
    };
    vector<node> st;
    int n, last=1;
    void init(int _n) {
        n = _n;
        st.resize(n*4*32);
    }
    void create(int v) {
        if (st[v].li) return;
        st[v].li = ++last;
        st[v].ri = ++last;
    }
    void relax(int l, int r, int v) {
        if (!st[v].lz) return;
        st[v].res = (r-l+1);
        if (l != r) {
            create(v);
            st[st[v].li].lz = 1;
            st[st[v].ri].lz = 1;
        }
        st[v].lz = 0;
    }
    void update(int ql, int qr, int l, int r, int v) {
        if (qr < l or r < ql) return;
        if (ql <= l and r <= qr) {
            st[v].lz = 1;
            relax(l, r, v);
            return;
        }
        create(v);
        int mid = (l+r)>>1;
        update(ql, qr, l, mid, st[v].li);
        update(ql, qr, mid+1, r, st[v].ri);
        st[v].res = st[st[v].li].res + st[st[v].ri].res;
    }
    int getans(int ql, int qr, int l, int r, int v) {
        relax(l, r, v);
        if (qr < l or r < ql) return 0;
        if (ql <= l and r <= qr) return st[v].res;
        create(v);
        int mid = (l+r)>>1;
        return getans(ql, qr, l, mid, st[v].li) + getans(ql, qr, mid + 1, r, st[v].ri);
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;
    SegTree st;
    st.init(100005);
    int c = 0, n = 100000001;
    while (q--) {
        int t, x, y;
        cin >> t >> x >> y;
        x += c;
        y += c;
        if (t == 1) {
            c = st.getans(x, y, 1, n, 1);
            cout << c << '\n';
        } else {
            st.update(x, y, 1, n, 1);
        }
    }
    return 0;
}

• Subtask 1: 0 / 100