Submission #728487

#	Time	Username	Problem	Language	Result	Execution time	Memory
728487		ismayil	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	622 ms	132952 KiB

apple

#pragma GCC target ("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int MOD = 1e9 + 7;
struct segtree{
    vector<int> tree, lazy, L, R;
    int size = 0;
    int create(){
        tree.push_back(0);
        lazy.push_back(0);
        L.push_back(0);
        R.push_back(0);
        return tree.size() - 1;
    }
    void init(int n){
        create();
        size = n;
        create();
    }
    void propagate(int x, int lx, int rx){
        if(lazy[x] == 0 || lx == rx) return;
        int mx = (lx + rx) / 2;
        if(!L[x]) L[x] = create();
        tree[L[x]] = mx - lx + 1;
        lazy[L[x]] = 1;
        if(!R[x]) R[x] = create();
        tree[R[x]] = rx - mx;
        lazy[R[x]] = 1;
        lazy[x] = 0;
    }
    void update(int l, int r, int x, int lx, int rx){
        propagate(x, lx, rx);
        if(r < lx || rx < l) return;
        if(l <= lx && rx <= r){
            tree[x] = rx - lx + 1;
            lazy[x] = 1;
            return;
        } 
        int mx = (lx + rx) / 2;
        if(!L[x]) L[x] = create();
        update(l, r, L[x], lx, mx);
        if(!R[x]) R[x] = create();
        update(l, r, R[x], mx + 1, rx);
        tree[x] = tree[L[x]] + tree[R[x]];
    }
    void update(int l, int r){
        update(l, r, 1, 1, size);
    }
    ll query(int l, int r, int x, int lx, int rx){
        propagate(x, lx, rx);
        if(r < lx || rx < l) return 0;
        if(l <= lx && rx <= r) return tree[x];
        int mx = (lx + rx) / 2;
        ll left = 0, right = 0;
        if(L[x]) left = query(l, r, L[x], lx, mx);
        if(R[x]) right = query(l, r, R[x], mx + 1, rx);
        return left + right;
    }
    ll query(int l, int r){
        return query(l, r, 1, 1, size);
    }
};
void solve(){
    int m;
    cin >> m;
    segtree st;
    st.init(1e9);
    int c = 0;
    while (m--)
    {
        int d, x, y;
        cin >> d >> x >> y;
        if(d == 1){
            c = st.query(x + c, y + c);
            cout << c << endl;
        }else st.update(x + c, y + c);
    }
    
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("output.txt", "w", stdout);
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i++){
        //printf("Case #%d: ", i);
        solve();
    }
}

• Subtask 1: 100 / 100