Submission #515826

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
515826	2022-01-19T20:46:16 Z	MohamedFaresNebili	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	385 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, 1000000007);
            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	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	22 ms	8552 KB	Output is correct
5	Correct	19 ms	10328 KB	Output is correct
6	Correct	19 ms	9904 KB	Output is correct
7	Correct	20 ms	10300 KB	Output is correct
8	Correct	159 ms	76912 KB	Output is correct
9	Correct	328 ms	130900 KB	Output is correct
10	Correct	344 ms	146900 KB	Output is correct
11	Correct	364 ms	159372 KB	Output is correct
12	Correct	366 ms	164816 KB	Output is correct
13	Correct	332 ms	205072 KB	Output is correct
14	Correct	335 ms	207216 KB	Output is correct
15	Runtime error	385 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-