Submission #498877

#	Time	Username	Problem	Language	Result	Execution time	Memory
498877		Bliznetc	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	518 ms	208732 KiB

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 (stderr)

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 / 100