Submission #888923

#	Time	Username	Problem	Language	Result	Execution time	Memory
888923		chuongdan	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	207 ms	235912 KiB

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 / 100