Submission #515825

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
515825	2022-01-19T20:43:39 Z	MohamedFaresNebili	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	376 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{
            int lb, rb, data = 0, lazy = 0;
            node *l = nullptr, *r = nullptr;
            node(int lb0, int rb0) {
                lb = lb0, rb = rb0;
            }
            void extend() {
                if(l == nullptr && lb != rb) {
                    int 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 -> l -> lazy = root -> lazy;
            root -> r -> lazy = root -> lazy;
            int 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, int lo, int 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, int lo, int 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);
            int q; cin >> q; ll c = 0; node* root = new node(0, 1e9);
            while(q--) {
                int 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	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	15 ms	8636 KB	Output is correct
5	Correct	19 ms	10532 KB	Output is correct
6	Correct	19 ms	10068 KB	Output is correct
7	Correct	20 ms	10416 KB	Output is correct
8	Correct	164 ms	77856 KB	Output is correct
9	Correct	356 ms	132708 KB	Output is correct
10	Correct	372 ms	148640 KB	Output is correct
11	Correct	375 ms	161204 KB	Output is correct
12	Correct	369 ms	166556 KB	Output is correct
13	Correct	336 ms	207096 KB	Output is correct
14	Correct	356 ms	209016 KB	Output is correct
15	Runtime error	376 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-