Submission #902952

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
902952	2024-01-11T04:56:29 Z	sverma22	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	365 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, 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; 
            // was something wrong here w/ the query ?!? 
            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);
    int t = 1; // cin >> t; 
    while(t--) {
        solve(); 
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	356 KB	Output is correct
3	Correct	0 ms	356 KB	Output is correct
4	Correct	13 ms	9496 KB	Output is correct
5	Correct	17 ms	11612 KB	Output is correct
6	Correct	16 ms	11108 KB	Output is correct
7	Correct	18 ms	11612 KB	Output is correct
8	Correct	163 ms	87884 KB	Output is correct
9	Correct	338 ms	152232 KB	Output is correct
10	Correct	347 ms	168456 KB	Output is correct
11	Correct	361 ms	180908 KB	Output is correct
12	Correct	341 ms	186720 KB	Output is correct
13	Correct	296 ms	217416 KB	Output is correct
14	Correct	329 ms	219316 KB	Output is correct
15	Runtime error	365 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-