Submission #515827

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
515827	2022-01-19T20:51:07 Z	MohamedFaresNebili	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	418 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 -> extend();
            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	0 ms	204 KB	Output is correct
4	Correct	16 ms	8524 KB	Output is correct
5	Correct	20 ms	10388 KB	Output is correct
6	Correct	19 ms	9992 KB	Output is correct
7	Correct	28 ms	10308 KB	Output is correct
8	Correct	165 ms	76860 KB	Output is correct
9	Correct	379 ms	130956 KB	Output is correct
10	Correct	355 ms	146832 KB	Output is correct
11	Correct	393 ms	159400 KB	Output is correct
12	Correct	371 ms	164768 KB	Output is correct
13	Correct	391 ms	204956 KB	Output is correct
14	Correct	355 ms	207100 KB	Output is correct
15	Runtime error	418 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-