Submission #1075172

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1075172	2024-08-25T19:21:18 Z	Sergio_2357	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	375 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	19 ms	8796 KB	Output is correct
5	Correct	23 ms	10580 KB	Output is correct
6	Correct	20 ms	10076 KB	Output is correct
7	Correct	21 ms	10584 KB	Output is correct
8	Correct	157 ms	77908 KB	Output is correct
9	Correct	331 ms	132580 KB	Output is correct
10	Correct	335 ms	148564 KB	Output is correct
11	Correct	375 ms	161324 KB	Output is correct
12	Correct	348 ms	166712 KB	Output is correct
13	Correct	331 ms	207184 KB	Output is correct
14	Correct	333 ms	209232 KB	Output is correct
15	Runtime error	356 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-