Submission #515834

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

        struct node{
            ll lb, rb; ll 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;
            ll a = md - (root -> lb) + 1, b = (root -> rb) - md;
            (root -> l) -> data = a;
            (root -> r) -> data = b;
            root -> lazy = 0;

        }
        void update(node* root, ll lo, ll hi, ll val) {
            prop(root);
            if(root -> lb > hi || root -> rb < lo) return;
            if(root -> lb >= lo && root -> rb <= hi) {
                root -> data = val * ((root -> rb) - (root -> lb) + 1); root -> lazy = val;
                prop(root); return;
            }
            root -> extend();
            update(root -> l, lo, hi, val);
            update(root -> r, lo, hi, val);
            root -> data = (root -> l) -> data + (root -> r) -> data;
        }
        ll query(node* root, ll lo, ll hi) {
            prop(root);
            if(root -> lb > hi || root -> rb < lo) return 0;
            if(root -> lb >= lo && root -> rb <= hi) return root -> data;
            root -> extend();
            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, c = 0; cin >> q; node* root = new node(0, 1000000000);
            while(q--) {
                ll d, lo, hi; cin >> d >> lo >> hi; lo += c; hi += c;
                if(d == 1) {
                  c = query(root, lo, hi);
                  cout << c << "\n";
                }
              	else update(root, lo, hi, 1);
            }
        }

• Subtask 1: 0 / 100