Submission #858530

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
858530	2023-10-08T15:47:45 Z	Requiem	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	331 ms	262144 KB

apple

#include<bits/stdc++.h>
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define fi first
#define se second
#define endl '\n'
#define TASKNAME "apple"
using namespace std;
struct SparseSegmentTree{
    int sum,lazy,l,r,toleft,toright;
    SparseSegmentTree(): sum(0), lazy(0), l(0), r(0), toleft(0), toright(0){}
    SparseSegmentTree(int l,int r): sum(0), lazy(0), l(l), r(r), toleft(0), toright(0){}
};
int cnt = 0,mid;
vector<SparseSegmentTree> st;
void push(int node){
     if (st[node].lazy==1){
            mid = (st[node].l + st[node].r)>>1;
            if (st[node].toleft == 0) {
                st[node].toleft = st.size();
                st.pb(SparseSegmentTree(st[node].l,mid));
            }
            if (st[node].toright == 0) {
                st[node].toright = st.size();
                st.pb(SparseSegmentTree(mid+1,st[node].r));
            }
            st[node].sum = st[node].r - st[node].l +1;
            st[st[node].toleft].lazy = st[st[node].toright].lazy = 1;;
            st[node].lazy = 0;

     }
}
void upd(int node,int u,int v){
    push(node);
    if (st[node].l > v or st[node].r < u) return;
    if (st[node].l >= u and st[node].r <=v) {
        st[node].lazy = 1;
        push(node);
        return;
    }
    mid = (st[node].l + st[node].r)>>1;
    if (st[node].toleft == 0) {
        st[node].toleft=st.size();
        st.pb(SparseSegmentTree(st[node].l,mid));
    }
    if (st[node].toright == 0) {
        st[node].toright=st.size();
        st.pb(SparseSegmentTree(mid+1,st[node].r));
    }
    upd(st[node].toleft,u,v);
    upd(st[node].toright,u,v);
    st[node].sum = st[st[node].toleft].sum + st[st[node].toright].sum;
}
int get(int node,int u,int v){
    push(node);
    if (st[node].l > v or st[node].r < u) return 0;
    if (st[node].l >= u and st[node].r <=v) return st[node].sum;
    mid = (st[node].l + st[node].r)>>1;
    if (st[node].toleft == 0) {
        st[node].toleft=st.size();
        st.pb(SparseSegmentTree(st[node].l,mid));
    }
    if (st[node].toright == 0) {
        st[node].toright=st.size();
        st.pb(SparseSegmentTree(mid+1,st[node].r));
    }
    return get(st[node].toleft,u,v) + get(st[node].toright,u,v);
}
int n,type,x,y;
main()
{
    fast;
    ///freopen(TASKNAME".inp","r",stdin);
    ///freopen(TASKNAME".out","w",stdout);

    cin>>n;
    int c = 0;
    cnt = 1;
    st.pb(SparseSegmentTree());
    st.pb(SparseSegmentTree(1,1e9));
    for(int i=1;i<=n;i++){
        cin>>type>>x>>y;
        if (type==1) {
            c = get(1,x+c,y+c);
            cout<<c<<endl;
        }
        else{
            upd(1,x+c,y+c);
        }
    }

}

Compilation message

apple.cpp:70:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   70 | main()
      | ^~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	13 ms	7144 KB	Output is correct
5	Correct	14 ms	8396 KB	Output is correct
6	Correct	14 ms	8140 KB	Output is correct
7	Correct	15 ms	7628 KB	Output is correct
8	Correct	102 ms	51616 KB	Output is correct
9	Correct	220 ms	100980 KB	Output is correct
10	Correct	216 ms	101116 KB	Output is correct
11	Correct	224 ms	100200 KB	Output is correct
12	Correct	220 ms	100084 KB	Output is correct
13	Correct	220 ms	199532 KB	Output is correct
14	Correct	225 ms	198228 KB	Output is correct
15	Runtime error	331 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-