Submission #515834

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
515834	2022-01-19T21:09:01 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()
        #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) {
            prop(root);
            if(root -> lb > hi || root -> rb < lo) return;
            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) {
            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, 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	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	17 ms	11296 KB	Output is correct
5	Correct	21 ms	13664 KB	Output is correct
6	Correct	22 ms	13176 KB	Output is correct
7	Correct	21 ms	13684 KB	Output is correct
8	Correct	190 ms	102392 KB	Output is correct
9	Correct	380 ms	174292 KB	Output is correct
10	Correct	389 ms	195604 KB	Output is correct
11	Correct	412 ms	212296 KB	Output is correct
12	Correct	418 ms	219528 KB	Output is correct
13	Runtime error	365 ms	262148 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-