Submission #515831

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
515831	2022-01-19T21:03:00 Z	MohamedFaresNebili	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	420 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) {
            if(root -> lazy) 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 = 1; prop(root); return;
            }
            root -> extend();
            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) {
            if(root -> lazy) 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; 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	0 ms	204 KB	Output is correct
4	Correct	17 ms	11340 KB	Output is correct
5	Correct	21 ms	13704 KB	Output is correct
6	Correct	21 ms	13220 KB	Output is correct
7	Correct	22 ms	13632 KB	Output is correct
8	Correct	185 ms	102324 KB	Output is correct
9	Correct	379 ms	174292 KB	Output is correct
10	Correct	420 ms	195520 KB	Output is correct
11	Correct	413 ms	212312 KB	Output is correct
12	Correct	413 ms	219472 KB	Output is correct
13	Runtime error	353 ms	262148 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-