Submission #498877

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
498877	2021-12-26T13:58:33 Z	Bliznetc	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	518 ms	208732 KB

apple

#include <bits/stdc++.h>

/*#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")*/

using namespace std;

#define pb push_back
#define sz size()
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define NULL nullptr

typedef pair < int, int > pii;
typedef vector < int >  vi;
typedef vector < vi >  vvi;

const int N = 1e9;

struct segTree{
    struct node{
        node *l, *r;
        int sum;
        bool flag;
        node () {
            l = r = NULL;
            sum = 0;
            flag = 0;
        }
    };

    node *root = new node();

    void push (node *v, int tl, int tr) {
        if (v->l == NULL) {
              v->l = new node();
        }
        if (v->r == NULL) {
            v->r = new node();
        }
        int mid = (tl + tr) / 2;
        v->l->sum = mid - tl + 1;
        v->r->sum = tr - mid;
        v->l->flag = v->r->flag = 1;
        v->flag = 0;
    }

    void update (node *v, int tl, int tr, int nl, int nr) {
        if (nl > tr || nr < tl) {
            return;
        }
        if (v->flag) {
            push (v, tl, tr);
        }
        if (tl >= nl && tr <= nr) {
            v->sum = tr - tl + 1;
            v->flag = 1;
            push(v, tl, tr);
            return;
        }
        int mid = (tl + tr) / 2;
        if (v->l == NULL) {
            v->l = new node;
        }
        if (v->r == NULL) {
            v->r = new node;
        }
        update (v->l, tl, mid, nl, nr);
        update (v->r, mid + 1, tr, nl, nr);
        v->sum = v->l->sum + v->r->sum;
    }

    int get (node *v, int tl, int tr, int nl, int nr) {
        if (nl > tr || nr < tl) {
            return 0;
        }
        if (v->flag) {
            push (v, tl, tr);
        }
        if (tl >= nl && tr <= nr) {
            return v->sum;
        }
        int mid = (tl + tr) / 2;
        if (v->l == NULL) {
            v->l = new node;
        }
        if (v->r == NULL) {
            v->r = new node;
        }
        return get (v->l, tl, mid, nl, nr) +
                get (v->r, mid + 1, tr, nl, nr);
    }

    int get_ans (int l, int r) {
        return get (root, 0, N, l, r);
    }

    void upd (int l, int r) {
        update(root, 0, N, l, r);
    }
};

segTree CST;

void solve () {
    int n, prev = 0;
    cin >> n;
    for (int it = 1; it <= n; it++) {
        int type;
        cin >> type;
        int l, r;
        cin >> l >> r;
        l += prev, r += prev;
        if (type == 1) {
            prev = CST.get_ans(l, r);
            cout << prev << "\n";
        }
        else {
            CST.upd(l, r);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //freopen ("f.in", "r", stdin);
    //freopen ("f.out", "w", stdout);
    int t = 1;
    while (t--) {
        solve();
        cout << "\n";
    }
}

Compilation message

apple.cpp:15: warning: "NULL" redefined
   15 | #define NULL nullptr
      | 
In file included from /usr/include/uchar.h:29,
                 from /usr/include/c++/10/cuchar:53,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:61,
                 from apple.cpp:1:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:392: note: this is the location of the previous definition
  392 | #define NULL __null
      |

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	14 ms	4920 KB	Output is correct
5	Correct	18 ms	6096 KB	Output is correct
6	Correct	18 ms	5836 KB	Output is correct
7	Correct	17 ms	5960 KB	Output is correct
8	Correct	142 ms	44984 KB	Output is correct
9	Correct	278 ms	78368 KB	Output is correct
10	Correct	310 ms	86372 KB	Output is correct
11	Correct	363 ms	92616 KB	Output is correct
12	Correct	332 ms	95380 KB	Output is correct
13	Correct	318 ms	110420 KB	Output is correct
14	Correct	281 ms	111556 KB	Output is correct
15	Correct	494 ms	202776 KB	Output is correct
16	Correct	492 ms	204224 KB	Output is correct
17	Correct	283 ms	115272 KB	Output is correct
18	Correct	312 ms	115292 KB	Output is correct
19	Correct	473 ms	208648 KB	Output is correct
20	Correct	518 ms	208732 KB	Output is correct