Submission #1075176

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1075176	2024-08-25T19:22:52 Z	Sergio_2357	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	498 ms	262144 KB

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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	17 ms	5980 KB	Output is correct
5	Correct	22 ms	6996 KB	Output is correct
6	Correct	19 ms	6864 KB	Output is correct
7	Correct	21 ms	7004 KB	Output is correct
8	Correct	141 ms	51424 KB	Output is correct
9	Correct	296 ms	87448 KB	Output is correct
10	Correct	299 ms	98152 KB	Output is correct
11	Correct	298 ms	106576 KB	Output is correct
12	Correct	325 ms	110212 KB	Output is correct
13	Correct	291 ms	137040 KB	Output is correct
14	Correct	292 ms	138316 KB	Output is correct
15	Correct	460 ms	254544 KB	Output is correct
16	Correct	466 ms	256596 KB	Output is correct
17	Correct	298 ms	145332 KB	Output is correct
18	Correct	318 ms	145492 KB	Output is correct
19	Correct	498 ms	262144 KB	Output is correct
20	Correct	460 ms	262144 KB	Output is correct