Submission #515838

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
515838	2022-01-19T21:13:16 Z	MohamedFaresNebili	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	355 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()
        #define lb lower_bound
        #define ub upper_bound

        struct node{
            ll lb, rb; ll 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;
            ll a = md - (root -> lb) + 1, b = (root -> rb) - md;
            (root -> l) -> data = a;
            (root -> r) -> data = b;
            root -> lazy = 0;

        }
        void update(node* root, ll lo, ll hi, ll val) {
            if(root -> lb > hi || root -> rb < lo) return;
            if(root -> lazy) prop(root);
            if(root -> lb >= lo && root -> rb <= hi) {
                root -> data = val * ((root -> rb) - (root -> lb) + 1); root -> lazy = val;
                prop(root); return;
            }
            root -> extend();
            update(root -> l, lo, hi, val);
            update(root -> r, lo, hi, val);
            root -> data = (root -> l) -> data + (root -> r) -> data;
        }
        ll query(node* root, ll lo, ll hi) {
            if(root -> lb > hi || root -> rb < lo) return 0;
            if(root -> lazy) prop(root);
            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, c = 0; cin >> q; node* root = new node(0, 1000000000);
            while(q--) {
                ll d, lo, hi; cin >> d >> lo >> hi; lo += c; hi += c;
                if(d == 1) {
                  c = query(root, lo, hi);
                  cout << c << "\n";
                }
              	else update(root, lo, hi, 1);
            }
        }

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	21 ms	8908 KB	Output is correct
5	Correct	19 ms	10736 KB	Output is correct
6	Correct	20 ms	10340 KB	Output is correct
7	Correct	18 ms	10768 KB	Output is correct
8	Correct	167 ms	81180 KB	Output is correct
9	Correct	355 ms	139460 KB	Output is correct
10	Correct	324 ms	155400 KB	Output is correct
11	Correct	343 ms	168036 KB	Output is correct
12	Correct	354 ms	173328 KB	Output is correct
13	Correct	312 ms	209404 KB	Output is correct
14	Correct	317 ms	211472 KB	Output is correct
15	Runtime error	333 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-