Submission #888921

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888921	2023-12-18T11:52:08 Z	chuongdan	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	1287 ms	262144 KB

apple

#include <bits/stdc++.h>
#define N 100000
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define int long long
#define rep(i, l, r) for(int i = l; i <= r; i++)

using namespace std;

typedef string str;
typedef pair<int,int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iv;

const int inf = 1e9;
const int MOD = 1e9 + 7;
const bool multi_test = false;

const string NAME = "VOI";

struct node {
    int sum, lazy, tl, tr, l, r;
    node() : sum(0), lazy(0), l(-1), r(-1) {}
};

struct sparse_segment_tree{
    int cnt;
    node st[30*N+5];

    void init(){
        cnt = 1;
        st[cnt].tl = 1;
        st[cnt].tr = 1e9;
    }

    void down_lazy(int id){
        if (st[id].lazy){
            int mid = (st[id].tl + st[id].tr) / 2;
            if (st[id].l == -1){
                st[id].l = ++cnt;
                st[cnt].tl = st[id].tl;
                st[cnt].tr = mid;
            }
            if (st[id].r == -1){
                st[id].r = ++cnt;
                st[cnt].tl = mid + 1;
                st[cnt].tr = st[id].tr;
            }
            st[st[id].l].sum = mid - st[id].tl + 1;
            st[st[id].r].sum = st[id].tr - mid;
            st[st[id].l].lazy = st[st[id].r].lazy = 1;
            st[id].lazy = 0;
        }
    }

    void update(int u, int v, int id = 1){
        int l = st[id].tl, r = st[id].tr;
        if (l > v || r < u) return;
        if (u <= l && r <= v) {
            st[id].sum = r - l + 1;
            st[id].lazy = 1;
            return;
        }
        int mid = (l + r) >> 1;
        down_lazy(id);
        if (st[id].l == -1){
            st[id].l = ++cnt;
            st[cnt].tl = l;
            st[cnt].tr = mid;
//            cout << "ADD " << cnt << " " << st[cnt].tl << " " << st[cnt].tr << endl;
        }
        if (st[id].r == -1){
            st[id].r = ++cnt;
            st[cnt].tl = mid + 1;
            st[cnt].tr = r;
//            cout << "ADD " << cnt << " " << st[cnt].tl << " " << st[cnt].tr << endl;
        }
//        cout << u << " " << v << " " << l << " " << r << " " << id << " " << st[id].l << " " << st[id].r << endl;
        update(u, v, st[id].l);
        update(u, v, st[id].r);
        st[id].sum = st[st[id].l].sum + st[st[id].r].sum;
    }

    int querry(int u, int v, int id = 1){
        int l = st[id].tl, r = st[id].tr;
        if (l > v || r < u) return 0;
        if (u <= l && r <= v) return st[id].sum;
        int mid = (l + r) >> 1;
        down_lazy(id);
        if (st[id].l == -1){
            st[id].l = ++cnt;
            st[cnt].tl = l;
            st[cnt].tr = mid;
        }
        if (st[id].r == -1){
            st[id].r = ++cnt;
            st[cnt].tl = mid + 1;
            st[cnt].tr = r;
        }
        return querry(u, v, st[id].l) + querry(u, v, st[id].r);
    }
};

int n;
sparse_segment_tree st;

void solve(){
    cin >> n;
    st.init();
    int c = 0;
    while (n--){
        int d, x, y;
        cin >> d >> x >> y;
        if (d == 1) {
            c = st.querry(x + c, y + c);
            cout << c << '\n';
        } else {
            st.update(x + c, y + c);
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    if (multi_test) cin >> t;
    while (t--) solve();
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	141136 KB	Output is correct
2	Correct	18 ms	141144 KB	Output is correct
3	Correct	18 ms	141148 KB	Output is correct
4	Correct	24 ms	141308 KB	Output is correct
5	Correct	26 ms	141356 KB	Output is correct
6	Correct	26 ms	141148 KB	Output is correct
7	Correct	26 ms	141300 KB	Output is correct
8	Correct	79 ms	141396 KB	Output is correct
9	Correct	157 ms	141624 KB	Output is correct
10	Correct	157 ms	141476 KB	Output is correct
11	Correct	163 ms	141652 KB	Output is correct
12	Correct	156 ms	141644 KB	Output is correct
13	Correct	141 ms	142160 KB	Output is correct
14	Correct	135 ms	141648 KB	Output is correct
15	Runtime error	1287 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-