Submission #1343844

#TimeUsernameProblemLanguageResultExecution timeMemory
1343844vpinxMonkey and Apple-trees (IZhO12_apple)C++20
100 / 100
408 ms205672 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e9;

struct node {
    int sum, lazy;
    node *left = nullptr, *right = nullptr;
    node(int lb, int rb) {
        sum = lazy = 0;
    }
    void extend(int li, int ri) {
        if (!left and li != ri) {
            int mid = (li + ri) / 2;
            left = new node(li, mid);
            right = new node(mid + 1, ri);
        }
    }
    void pd(int li, int ri) {
        if (li != ri and lazy == 1) {
            if (!left) extend(li, ri);
            left->lazy = right->lazy = 1;
        }
        lazy = 0;
    }
    void push(int li, int ri) {
        if (lazy != 0) sum = (ri - li + 1);
    }
    void add(int l, int r, int li, int ri) {
        push(li, ri);
        if (r < li or ri < l) return;
        if (l <= li and ri <= r) {
            lazy = 1;
            push(li, ri);
            return;
        }
        if (!left) extend(li, ri);
        pd(li, ri);
        
        int mid = (li + ri) / 2;
        left->add(l, r, li, mid);
        right->add(l, r, mid + 1, ri);
        sum = left->sum + right->sum;
    }
    int query(int l, int r, int li, int ri) {
        push(li, ri);
        if (r < li or ri < l) return 0;
        if (l <= li and ri <= r) return sum;
        if (!left) extend(li, ri);
        pd(li, ri);
        int mid = (li + ri) / 2;
        return left->query(l, r, li, mid) + right->query(l, r, mid + 1, ri); 
    }
};

void solve() {
    int q;
    cin >> q;
    
    int c = 0;
    node root(0, N);
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        l += c - 1, r += c - 1;
        if (t == 1) {
            c = root.query(l, r, 0, N - 1);
            cout << c << "\n";
        }else root.add(l, r, 0, N - 1);
    }
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...