Submission #903143

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
903143	2024-01-11T05:53:32 Z	sverma22	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	340 ms	262144 KB

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;
    bool 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) && (node->st != node->en)) {
                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) {
            if(node->lazy != 0) {
                node->sum = (node->en - node->st + 1) * node->lazy; 
                if(node->st != node->en) {
                    extend(node); 
                    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) { 
                    extend(node); 
                    node->left_child->lazy = val; 
                    node->right_child->lazy = val; 
                }
                return; 
            }
            extend(node); 
            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) {
            if(node->lazy != 0) {
                node->sum = (node->en - node->st + 1) * node->lazy; 
                if(node->st != node->en) {
                    extend(node); 
                    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; 
            extend(node); 
            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) {
            c = st.query(a + c, b + c, st.root); 
            cout << c << '\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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	13 ms	8504 KB	Output is correct
5	Correct	16 ms	10484 KB	Output is correct
6	Correct	16 ms	10072 KB	Output is correct
7	Correct	18 ms	10332 KB	Output is correct
8	Correct	137 ms	77140 KB	Output is correct
9	Correct	277 ms	130904 KB	Output is correct
10	Correct	308 ms	146952 KB	Output is correct
11	Correct	324 ms	159508 KB	Output is correct
12	Correct	317 ms	165016 KB	Output is correct
13	Correct	316 ms	205016 KB	Output is correct
14	Correct	300 ms	207096 KB	Output is correct
15	Runtime error	340 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-