Submission #1278025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278025		yazansh	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	310 ms	205552 KiB

apple

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define all(a) a.begin(),a.end()
const int LOG=31;
const int mxn=2e9+5;
const ll inf =1e18;
const int mod=998244353;
struct dsegtree{
    int mx;
    struct node
    {
        ll s=0, lz = 0;
        node *l=nullptr, *r = nullptr;
    };
    node *root;
    dsegtree(int n)
    {
        mx = n;
        root = new node;
    }
    void apply(node *cur,ll sz,ll v ){
        if(v==1){
            cur->lz = 1;
            cur->s = sz * v;
        }
    }
    void push(node *cur,int lx,int rx){
        if(cur->l==nullptr)
            cur->l = new node;
        if(cur->r==nullptr)
            cur->r = new node;
        int mid = lx + (rx - lx) / 2;
        apply(cur->l, mid-lx+1, cur->lz);
        apply(cur->r, rx-mid, cur->lz);
    }
    void update(node *cur,int lx,int rx,int l,int r,int v){
        if(lx>r||rx<l)
            return;
        if(l<=lx&&rx<=r){
            apply(cur, rx - lx + 1, v);
            return;
        }
        int mid = lx + (rx - lx) / 2;
        push(cur, lx, rx);
        update(cur->l, lx, mid, l, r, v);
        update(cur->r, mid + 1, rx, l, r, v);
        cur->s = cur->l->s + cur->r->s;
    }
    int query(node * cur,int lx,int rx,int l,int r){
        if(lx>r||rx<l)
            return 0;
        if(l<=lx&&rx<=r){
            return cur->s;
        }
        int mid = lx + (rx - lx) / 2;
        push(cur, lx, rx);
        return query(cur->l, lx, mid, l, r)+query(cur->r, mid + 1, rx, l, r);
    }
    void update(int l,int r,int val){
        update(root, 0, mx - 1, l, r, val);
    }
    int query(int l,int r){
        return query(root, 0, mx - 1, l, r);
    }
};
void solve(){
    int q;
    cin >> q;
    dsegtree st(mxn);
    int c = 0;
    while (q--)
    {
        int op, l, r;
        cin >> op >> l >> r;
        if(op==1){
            c = st.query(l + c, r + c);
            cout << c << "\n";
        }
        else
        {
            st.update(l + c, r + c, 1);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef Usaco
    string f="shortcut";
    freopen((f+".in").c_str(),"r",stdin);
    freopen((f+".out").c_str(),"w",stdout);
#endif
    ll tt = 1;
   // cin >> tt;
    while (tt--){
        solve();
        //cout<<"\n";
    }
}

• Subtask 1: 100 / 100