Submission #902909

#	Time	Username	Problem	Language	Result	Execution time	Memory
902909		sverma22	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1 ms	348 KiB

apple

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

// #define int int64_t

int m; 
vector<array<int, 3> > events; 
vector<pair<int, int> > ranges; 

struct Node {
    int st, en; 
    int sum, lazy; 
    Node *left_child, *right_child; 
    Node(int s, int e) {
        st = s; 
        en = e; 
        sum = lazy = 0; 
        left_child = nullptr; 
        right_child = nullptr; 
    }
}; 

class SegTree {
    public: 
        Node* root; 
        SegTree() {
            root = new Node(1, 1e9); 
        }

        void extend(Node* node) {
            if(node->left_child == nullptr) {
                int mid = (node->st + node->en) / 2; 
                node->left_child = new Node(node->st, mid); 
                node->right_child = new Node(mid + 1, node->en); 
            }
        }

        void range_set(int l, int r, int val, Node* node) {
            extend(node); 
            // PROPOGATE 
            if(node->lazy != 0) {
                node->sum = (node->en - node->st + 1) * node->lazy; 
                if(node->st != node->en) {
                    node->left_child->lazy += node->lazy; 
                    node->right_child->lazy += node->lazy; 
                }
                node->lazy = 0; 
            }

            if(node->en < l || node->st > r) return; 
            if(l <= node->st && node->en <= r) {
                node->sum = (node->en - node->st + 1) * val; 
                if(node->st != node->en) { 
                    node->left_child->lazy += val; 
                    node->right_child->lazy += val; 
                }
                return; 
            }

            range_set(l, r, val, node->left_child); 
            range_set(l, r, val, node->right_child); 
            node->sum = node->left_child->sum + node->right_child->sum; 
        }

        int query(int l, int r, Node* node) {
            extend(node); 
            // PROPOGATE 
            if(node->lazy != 0) {
                node->sum = (node->en - node->st + 1) * node->lazy; 
                if(node->st != node->en) {
                    node->left_child->lazy += node->lazy; 
                    node->right_child->lazy += node->lazy; 
                }
                node->lazy = 0; 
            }

            if(node->en < l || node->st > r) return 0; 
            if(l <= node->st && node->en <= r) return node->sum; 
            return query(l, r, node->left_child) + query(l, r, node->right_child); 
        }

}; 


void solve() {
    cin >> m; 
    
    SegTree st; 

    int c = 0; 
    for(int i = 0; i < m; i++) {
        int type, a, b; cin >> type >> a >> b; 
        if(type == 1) {
            int x = st.query(a + c, b + c, st.root); 
            c = x; 
            cout << x << '\n';
        } else {
            st.range_set(a + c, b + c, 1, st.root); 
        }
    }


}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // #ifndef ONLINE_JUDGE
    // freopen("file.txt", "r", stdin);
    // #endif
    int t = 1; // cin >> t; 
    while(t--) {
        solve(); 
    }
}

• Subtask 1: 0 / 100