Submission #1206917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206917		liangjeremy	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	219 ms	132352 KiB

apple

#include<bits/stdc++.h>
#include<random>
#define fi first
#define se second
using namespace std;
using db=double;
using ll=long long;
using sll=__int128;//super long long
using lb=long double;//lb is slow
//numbers for hashing: b(19260817),mod(998244353)
//another number for hashing:b(137) only
// freopen("deleg.in", "r", stdin);
// freopen("deleg.out", "w", stdout);

class Dynamic{
    private:
        struct node{
            int sum=0; int lazy=0;
            int left=-1; int right=-1;
        };
        vector<node>tree; const int n; int timer=1;
    public:
        Dynamic(int n):n(n){
            tree.push_back(node()); tree.push_back(node());
        }
        void pushdown(int rt, int l, int mid, int r){
            if(tree[rt].left==-1){
                tree.push_back(node());
                timer++; tree[rt].left=timer;
            }
            if(tree[rt].right==-1){
                tree.push_back(node());
                timer++; tree[rt].right=timer;
            }
            if(tree[rt].lazy){
                tree[tree[rt].left].lazy=tree[rt].lazy;
                tree[tree[rt].left].sum=tree[rt].lazy*(mid-l+1);
                tree[tree[rt].right].lazy=tree[rt].lazy;
                tree[tree[rt].right].sum=tree[rt].lazy*(r-mid);
                tree[rt].lazy=0;
            }
        }   
        void update(int l, int r, int rt, int L, int R, int x){
            if(L<=l && r<=R){
                tree[rt].lazy=x; tree[rt].sum=x*(r-l+1); return;
            }
            int mid=(l+r)>>1; pushdown(rt,l,mid,r);
            if(L<=mid)update(l,mid,tree[rt].left,L,R,x);
            if(R>mid)update(mid+1,r,tree[rt].right,L,R,x);
            tree[rt].sum=tree[tree[rt].left].sum+tree[tree[rt].right].sum;
        }
        int query(int l, int r, int rt, int L, int R){
            if(L<=l && r<=R)return tree[rt].sum;
            int mid=(l+r)>>1; pushdown(rt,l,mid,r); int ans=0;
            if(L<=mid)ans+=query(l,mid,tree[rt].left,L,R);
            if(R>mid)ans+=query(mid+1,r,tree[rt].right,L,R);
            return ans;
        }
};

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q; cin>>q; int ans=0; 
    const int MAXN=1e9+10; Dynamic segtree(MAXN);
    while(q--){
        int op,x,y; cin>>op>>x>>y; 
        if(op==2){
            segtree.update(1,MAXN,1,x+ans,y+ans,1);
        }else{
            ans=segtree.query(1,MAXN,1,x+ans,y+ans); cout<<ans<<'\n';
        }
    }
}

• Subtask 1: 100 / 100