Submission #515841

#	Time	Username	Problem	Language	Result	Execution time	Memory
515841		MohamedFaresNebili	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	426 ms	208864 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()
        #define lb lower_bound
        #define ub upper_bound

        struct seg{
            struct node{
                node *l = nullptr, *r = nullptr;
                int data = 0; bool lazy = false;
            };

            node *root = new node();

            void prop(node *v, int l, int r) {
                if(!v -> l) v -> l = new node();
                if(!v -> r) v -> r = new node();
                int md =(l + r) / 2;
                v -> l -> data = md - l + 1;
                v -> r -> data = r - md;
                v -> lazy = false;
                v -> l -> lazy = v ->r -> lazy = true;
            }
            void update(node *v, int l, int r, int lo, int hi) {
                if(l > hi || r < lo) return;
                if(v -> lazy) prop(v, l, r);
                if(l >= lo && r <= hi) {
                    v -> data = r - l + 1;
                    v -> lazy = true;
                    prop(v, l, r);
                    return;
                }
                int md = (l + r) / 2;
                if(!v -> l) v -> l = new node();
                if(!v -> r) v -> r = new node();
                update(v -> l, l, md, lo, hi);
                update(v -> r, md + 1, r, lo, hi);
                v -> data = v -> l -> data + v -> r -> data;
            }
            int query(node *v, int l, int r, int lo, int hi) {
                if(l > hi || r < lo) return 0;
                if(v -> lazy) prop(v, l, r);
                if(l >= lo && r <= hi) return v -> data;
                int md = (l + r) / 2;
                if(!v -> l) v -> l = new node();
                if(!v -> r) v -> r = new node();
                return query(v -> l, l, md, lo, hi) + query(v -> r, md + 1, r, lo, hi);
            }
            void update(int lo, int hi) { update(root, 0, 1000000007, lo, hi); }
            int query(int lo, int hi) { return query(root, 0, 1000000007, lo, hi); }
        };

        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            int q; cin >> q;
            int c = 0;
            seg st;
            while(q--) {
                int d, l, r; cin >> d >> l >> r;
                l += c; r += c;
                if(d == 1) {
                    c = st.query(l, r);
                    cout << c << "\n";
                }
                else st.update(l, r);
            }
        }

• Subtask 1: 100 / 100