답안 #888923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888923	2023-12-18T11:53:03 Z	chuongdan	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	207 ms	235912 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[50*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

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	235088 KB	Output is correct
2	Correct	29 ms	235140 KB	Output is correct
3	Correct	30 ms	235092 KB	Output is correct
4	Correct	36 ms	235092 KB	Output is correct
5	Correct	38 ms	235248 KB	Output is correct
6	Correct	38 ms	235084 KB	Output is correct
7	Correct	38 ms	235276 KB	Output is correct
8	Correct	89 ms	235408 KB	Output is correct
9	Correct	169 ms	235504 KB	Output is correct
10	Correct	184 ms	235780 KB	Output is correct
11	Correct	173 ms	235584 KB	Output is correct
12	Correct	171 ms	235536 KB	Output is correct
13	Correct	149 ms	235608 KB	Output is correct
14	Correct	147 ms	235528 KB	Output is correct
15	Correct	205 ms	235664 KB	Output is correct
16	Correct	207 ms	235600 KB	Output is correct
17	Correct	152 ms	235788 KB	Output is correct
18	Correct	145 ms	235536 KB	Output is correct
19	Correct	203 ms	235544 KB	Output is correct
20	Correct	201 ms	235912 KB	Output is correct