Submission #515841

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
515841	2022-01-19T21:24:28 Z	MohamedFaresNebili	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	426 ms	208864 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 seg{
            struct node{
                node *l = nullptr, *r = nullptr;
                int data = 0; bool lazy = false;
            };

            node *root = new node();

            void prop(node *v, int l, int r) {
                if(!v -> l) v -> l = new node();
                if(!v -> r) v -> r = new node();
                int md =(l + r) / 2;
                v -> l -> data = md - l + 1;
                v -> r -> data = r - md;
                v -> lazy = false;
                v -> l -> lazy = v ->r -> lazy = true;
            }
            void update(node *v, int l, int r, int lo, int hi) {
                if(l > hi || r < lo) return;
                if(v -> lazy) prop(v, l, r);
                if(l >= lo && r <= hi) {
                    v -> data = r - l + 1;
                    v -> lazy = true;
                    prop(v, l, r);
                    return;
                }
                int md = (l + r) / 2;
                if(!v -> l) v -> l = new node();
                if(!v -> r) v -> r = new node();
                update(v -> l, l, md, lo, hi);
                update(v -> r, md + 1, r, lo, hi);
                v -> data = v -> l -> data + v -> r -> data;
            }
            int query(node *v, int l, int r, int lo, int hi) {
                if(l > hi || r < lo) return 0;
                if(v -> lazy) prop(v, l, r);
                if(l >= lo && r <= hi) return v -> data;
                int md = (l + r) / 2;
                if(!v -> l) v -> l = new node();
                if(!v -> r) v -> r = new node();
                return query(v -> l, l, md, lo, hi) + query(v -> r, md + 1, r, lo, hi);
            }
            void update(int lo, int hi) { update(root, 0, 1000000007, lo, hi); }
            int query(int lo, int hi) { return query(root, 0, 1000000007, lo, hi); }
        };

        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            int q; cin >> q;
            int c = 0;
            seg st;
            while(q--) {
                int d, l, r; cin >> d >> l >> r;
                l += c; r += c;
                if(d == 1) {
                    c = st.query(l, r);
                    cout << c << "\n";
                }
                else st.update(l, r);
            }
        }

Subtask #1

100.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	12 ms	4920 KB	Output is correct
5	Correct	15 ms	5912 KB	Output is correct
6	Correct	20 ms	5680 KB	Output is correct
7	Correct	15 ms	5904 KB	Output is correct
8	Correct	132 ms	44036 KB	Output is correct
9	Correct	259 ms	76644 KB	Output is correct
10	Correct	275 ms	84644 KB	Output is correct
11	Correct	265 ms	90916 KB	Output is correct
12	Correct	276 ms	93644 KB	Output is correct
13	Correct	266 ms	108452 KB	Output is correct
14	Correct	253 ms	109560 KB	Output is correct
15	Correct	417 ms	202616 KB	Output is correct
16	Correct	422 ms	204200 KB	Output is correct
17	Correct	258 ms	115276 KB	Output is correct
18	Correct	281 ms	115492 KB	Output is correct
19	Correct	410 ms	208640 KB	Output is correct
20	Correct	426 ms	208864 KB	Output is correct