Submission #515829

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
515829	2022-01-19T20:53:22 Z	MohamedFaresNebili	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	465 ms	262148 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	25 ms	11320 KB	Output is correct
5	Correct	32 ms	13664 KB	Output is correct
6	Correct	25 ms	13172 KB	Output is correct
7	Correct	22 ms	13704 KB	Output is correct
8	Correct	193 ms	102360 KB	Output is correct
9	Correct	389 ms	174328 KB	Output is correct
10	Correct	397 ms	195576 KB	Output is correct
11	Correct	460 ms	212288 KB	Output is correct
12	Correct	465 ms	219596 KB	Output is correct
13	Runtime error	379 ms	262148 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-