Submission #903131

# Submission time Handle Problem Language Result Execution time Memory
903131 2024-01-11T05:48:46 Z sverma22 Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
358 ms 262144 KB
#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) {
            extend(node); 
            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); 
            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) {
            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(); 
    }
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 14 ms 8808 KB Output is correct
5 Correct 16 ms 10700 KB Output is correct
6 Correct 15 ms 10308 KB Output is correct
7 Correct 25 ms 10600 KB Output is correct
8 Correct 137 ms 77764 KB Output is correct
9 Correct 324 ms 131996 KB Output is correct
10 Correct 312 ms 147856 KB Output is correct
11 Correct 340 ms 160524 KB Output is correct
12 Correct 328 ms 165920 KB Output is correct
13 Correct 342 ms 206276 KB Output is correct
14 Correct 328 ms 208396 KB Output is correct
15 Runtime error 358 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -