Submission #515829

#	Time	Username	Problem	Language	Result	Execution time	Memory
515829		MohamedFaresNebili	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	465 ms	262148 KiB

apple

#include <bits/stdc++.h>

        using namespace std;

        using ll = long long;
        using ii = pair<ll, ll>;
        using vi = vector<int>;

        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) x.begin(), x.end()

        struct node{
            ll lb, rb, data = 0, lazy = 0;
            node *l = nullptr, *r = nullptr;
            node(ll lb0, ll rb0) {
                lb = lb0, rb = rb0;
            }
            void extend() {
                if(l == nullptr && lb != rb) {
                    ll md = (lb + rb) / 2;
                    l = new node(lb, md);
                    r = new node(md + 1, rb);
                }
            }
        };

        void prop(node* root) {
            if(root -> lb == root -> rb || root -> lazy == 0) return;
            root -> extend();
            root -> l -> lazy = root -> lazy;
            root -> r -> lazy = root -> lazy;
            ll md = (root -> lb + root -> rb) / 2;
            root -> l -> data = (md - root -> lb + 1);
            root -> r -> data = (root -> rb - md);
            root -> lazy = 0;
        }
        void update(node* root, ll lo, ll hi) {
            root -> extend(); prop(root);
            if(root -> lb > hi || root -> rb < lo) return;
            if(root -> lb >= lo && root -> rb <= hi) {
                root -> data = (root -> rb) - (root -> lb) + 1;
                root -> lazy++; prop(root); return;
            }
            update(root -> l, lo, hi);
            update(root -> r, lo, hi);
            root -> data = (root -> l) -> data + (root -> r) -> data;
        }
        ll query(node* root, ll lo, ll hi) {
            root -> extend(); prop(root);
            if(root -> lb > hi || root -> rb < lo) return 0;
            if(root -> lb >= lo && root -> rb <= hi) return root -> data;
            return query(root -> l, lo, hi) + query(root -> r, lo, hi);
        }

        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            ll q; cin >> q; ll c = 0; node* root = new node(0, 1e9 + 5);
            while(q--) {
                ll d, l, r; cin >> d >> l >> r;
                if(d == 1) {
                    ll res = query(root, l + c, r + c); c = res;
                    cout << res << "\n";
                }
                else if(d == 2) update(root, l + c, r + c);
            }
            return 0;
        }

• Subtask 1: 0 / 100