답안 #858530

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
858530 2023-10-08T15:47:45 Z Requiem 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
331 ms 262144 KB
#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()
      | ^~~~
# 결과 실행 시간 메모리 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 -