답안 #902952

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
902952 2024-01-11T04:56:29 Z sverma22 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
365 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, 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(); 
    }
}
# 결과 실행 시간 메모리 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 -