Submission #1313707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313707		ladnoooo	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	219 ms	137456 KiB

apple

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

#define int long long
#define pb push_back

const int maxN = 1e5 + 7;

int t[maxN * 60], lz[maxN * 60];

int lc[maxN * 60], rc[maxN * 60];

int ptr = 1;

int new_node() {
    ++ptr;
    t[ptr] = 0;
    lz[ptr] = -1;
    lc[ptr] = rc[ptr] = 0;
    return ptr;
}

void push(int v, int tl, int tr) {
    if (lz[v] == -1 || tl == tr) return;

    int tm = (tl + tr) / 2;

    if (!lc[v]) lc[v] = new_node();
    if (!rc[v]) rc[v] = new_node();

    int val = lz[v];

    t[lc[v]] = (tm - tl + 1) * val;
    t[rc[v]] = (tr - tm) * val;

    lz[lc[v]] = val;
    lz[rc[v]] = val;

    lz[v] = -1;
}

void upd(int v, int tl, int tr, int l, int r, int val) { 
    if(tl > r || tr < l) return;
    if(l <= tl && tr <= r) {
        t[v] = (tr - tl + 1) * val;
        lz[v] = val;
        return;
    }
     push(v, tl, tr);
    int tm = (tl + tr) / 2;
    if(!lc[v]) lc[v] = new_node();
    if(!rc[v]) rc[v] = new_node();
    upd(lc[v], tl, tm, l, r, val);
    upd(rc[v], tm + 1, tr, l, r, val);
    t[v] = t[lc[v]] + t[rc[v]];
}

int get(int v, int tl, int tr, int l, int r) {
    if (!v || r < tl || tr < l) return 0;
    if (l <= tl && tr <= r) return t[v];
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    return get(lc[v], tl, tm, l, r) + get(rc[v], tm + 1, tr, l, r);
}

void solve() {
    int q;
    cin >> q;
    int c = 0;
    while(q--) {
        int t, l, r;
        cin >> t >> l >> r;
        if(t == 1) {
            int res = get(1, -1e9, 1e9, l + c, r + c);
            c = res;
            cout << res << '\n';
        } else {
            upd(1, -1e9, 1e9, l + c, r + c, 1);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("input.txt", "r", stdin);
    int t = 1;
    //cin >> t;
    while(t--) solve();
}

• Subtask 1: 100 / 100