Submission #1075172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075172		Sergio_2357	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	375 ms	262144 KiB

apple

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC target("avx2")
//#pragma GCC optimization("Ofast")

#define int long long
#define F first
#define S second
#define all(a) a.begin(), a.end()
#define vx vector
#define px pair

#define double long double

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<vii> viii;
typedef vector<viii> viiii;

template <class T>
void read(T& x)
{
    cin >> x;
}

template <class T, class M>
void read(px<T, M>& p)
{
    T a;
    M b;
    read(a);
    read(b);
    p = { a, b };
}

template <class T>
void read(vx<T>& v)
{
    for (int i = 0; i < v.size(); i++)
        read(v[i]);
}

template <class T>
void print(T x)
{
    cout << x;
}

template <class T, class M>
void print(px<T, M> v)
{
    print(v.F);
    print(' ');
    print(v.S);
    print("; ");
}

template <class T>
void print(vx<T> v)
{
    for (T x : v) {
        print(x);
        cout << ' ';
    }
    cout << endl;
}

struct SegTree {

    struct Node {
        int v = 0;
        int lz = 0;
        Node* L = NULL;
        Node* R = NULL;
    };

    typedef Node* pnode;

    pnode R = NULL;
    int n;

    void push_lz(pnode i, int l, int r) {
        if (!i) return;
        if (r-l <= 1) return;
        if (i->L == NULL) {
            i->L = new Node;
        }
        if (i->R == NULL) {
            i->R = new Node;
        }
        if (i->lz != 0) {
            int m = (r+l)/2;
            i->L->lz = i->lz;
            i->L->v = (m-l)*i->lz;
            i->R->lz = i->lz;
            i->R->v = (r-m)*i->lz;
            i->lz = 0;
        }
    }

    SegTree(int n) {
        this -> n = n;
        R = new Node;
    }

    void set(pnode i, int l, int r, int ql, int qr, int x) {
        if (!i) return;
        push_lz(i, l, r);
        //cout << l << ' ' << r << endl;
        if (ql <= l && r <= qr) {
            i->lz = x;
            i->v = (r-l)*x;
            return;
        }
        if (r <= ql || qr <= l) {
            return;
        }
        int m = (r+l)/2;
        set(i->L, l, m, ql, qr, x);
        set(i->R, m, r, ql, qr, x);
        i->v = i->L->v + i->R->v;
    }

    void set(int l, int r, int x) {
        //cout << 'a' << endl;
        set(this->R, 0, n, l, r, x);
        //cout << 'b' << endl;

    }

    int sum(pnode i, int l, int r, int ql, int qr) {
        if (!i) return 0;
        push_lz(i, l, r);
        //cout << l << ' ' << r << endl;
        if (ql <= l && r <= qr) {
            return i->v;
        }
        if (r <= ql || qr <= l) {
            return 0;
        }
        int m = (r+l)/2;
        return sum(i->L, l, m, ql, qr) +
                sum(i->R, m, r, ql, qr);
    }

    int sum(int l, int r) {
        //cout << 'c' << endl;
        return sum(this->R, 0, n, l, r);
    }

};

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int M;
    cin >> M;
    SegTree st(1e9+100);
    int C = 0;
    while (M--) {
        int t, l, r;
        cin >> t >> l >> r;
        l += C;
        r += C;
        if (t == 2) {
            st.set(l-1, r, 1);
        } else {
            C = st.sum(l-1, r);
            cout << C << endl;
            //cout << 'd' << endl;

        }
    }
}

• Subtask 1: 0 / 100