Submission #1268646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268646		arwakhattab	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	321 ms	148468 KiB

apple

#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const char nl = '\n', sp = ' ';

template<typename T>
struct dynamic_segment_tree {
    T N;
    using node = array<T, 3>; // left, right, val
    vector<node> sg;
    vector<T> lz;
    T sg_eye{0}, lz_eye{-1};

#define ul sg[u][0]
#define ur sg[u][1]
#define ux sg[u][2]

    dynamic_segment_tree(T n) : N(n) {
        sg.emplace_back();
        lz.emplace_back(lz_eye);
    }

    void push(int u, T l, T r) {
        if (lz[u] == lz_eye) return;
        ux = lz[u] * (r - l + 1);
        if (l != r) {
            if (!ul) {
                ul = sg.size(), sg.emplace_back(), lz.emplace_back(lz_eye);
            }
            if (!ur) {
                ur = sg.size(), sg.emplace_back(), lz.emplace_back(lz_eye);
            }
            lz[ul] = lz[u];
            lz[ur] = lz[u];
        }
        lz[u] = lz_eye;
    }

    T merge(T a, T b) {
        return a + b;
    }

    void update(T ql, T qr, T val, int u = 0, T l = 0, T r = -1) {
        if (r == -1) r += N;
        push(u, l, r);
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            lz[u] = val;
            push(u, l, r);
            return;
        }
        T mid = (l + r) >> 1;
        if (!ul) {
            ul = sg.size(), sg.emplace_back(), lz.emplace_back(lz_eye);
        }
        update(ql, qr, val, ul, l, mid);
        if (!ur) {
            ur = sg.size(), sg.emplace_back(), lz.emplace_back(lz_eye);
        }
        update(ql, qr, val, ur, mid + 1, r);
        ux = merge(sg[ul][2], sg[ur][2]);
    }

    T query(T ql, T qr, int u = 0, T l = 0, T r = -1) {
        if (r == -1) r += N;
        if (l > qr || r < ql) return sg_eye;
        push(u, l, r);
        if (l >= ql && r <= qr) return ux;
        T mid = (l + r) >> 1;
        T ansL = sg_eye, ansR = sg_eye;
        if (ql <= mid) {
            if (!ul) {
                ul = sg.size(), sg.emplace_back(), lz.emplace_back(lz_eye);
            }
            ansL = query(ql, qr, ul, l, mid);
        }
        if (qr >= mid + 1) {
            if (!ur) {
                ur = sg.size(), sg.emplace_back(), lz.emplace_back(lz_eye);
            }
            ansR = query(ql, qr, ur, mid + 1, r);
        }
        return merge(ansL, ansR);
    }
};

void solve() {
    int q;
    cin >> q;
    dynamic_segment_tree<int> sg(1e9 + 5);
    int c = 0;
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) {
            cout << (c = sg.query(l + c, r + c)) << nl;
        } else {
            sg.update(l + c, r + c, 1);
        }
    }
}

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

#ifdef LOCAL
    freopen("../in.txt", "r", stdin);
    freopen("../out.txt", "w", stdout);
#endif

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 100 / 100