Submission #674754

#	Time	Username	Problem	Language	Result	Execution time	Memory
674754		onlk97	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	589 ms	200368 KiB

apple

#include <bits/stdc++.h>
#define int long long
#define double long double
#define x first
#define y second
#define pb push_back
#define dbg(A) cout<<(#A)<<" has value "<<A<<'\n';
#define dbgv(A) cout<<(#A)<<" has values ";for(auto&i:A)cout<<i<<' ';cout<<'\n';
#define dbgp(A) cout<<(#A)<<" has values ";for(auto&i:A)cout<<i.first<<", "<<i.second<<"   ";cout<<'\n';
using namespace std;
using pii=pair <int,int>;
using tii=pair <pii,int>;
using qii=pair <pii,pii>;
mt19937 mt(time(nullptr));
vector <int> seg,laz,lc,rc,marked;
void pushdown(int id,int tl,int tr){
    int tm=(tl+tr)/2;
    if (!lc[id]){
        lc[id]=lc.size();
        seg.pb(0); laz.pb(0); lc.pb(0); rc.pb(0); marked.pb(0);
    }
    if (!rc[id]){
        rc[id]=rc.size();
        seg.pb(0); laz.pb(0); lc.pb(0); rc.pb(0); marked.pb(0);
    }
    if (!marked[id]) return;
    seg[lc[id]]=laz[id]*(tm-tl+1);
    seg[rc[id]]=laz[id]*(tr-tm);
    laz[lc[id]]=laz[id];
    laz[rc[id]]=laz[id];
    marked[lc[id]]=1;
    marked[rc[id]]=1;
    marked[id]=0;
}
void update(int id,int tl,int tr,int l,int r,int val){
    if (l>r) return;
    if (l<=tl&&tr<=r){
        seg[id]=(tr-tl+1)*val;
        laz[id]=val;
        marked[id]=1;
        return;
    }
    pushdown(id,tl,tr);
    int tm=(tl+tr)/2;
    if (lc[id]) update(lc[id],tl,tm,l,min(r,tm),val);
    if (rc[id]) update(rc[id],tm+1,tr,max(l,tm+1),r,val);
    seg[id]=(lc[id]?seg[lc[id]]:0ll)+(rc[id]?seg[rc[id]]:0ll);
}
int query(int id,int tl,int tr,int l,int r){
    if (l>r) return 0;
    if (l<=tl&&tr<=r) return seg[id];
    pushdown(id,tl,tr);
    int tm=(tl+tr)/2;
    int lx=(lc[id]?query(lc[id],tl,tm,l,min(r,tm)):0ll);
    int rx=(lc[id]?query(rc[id],tm+1,tr,max(l,tm+1),r):0ll);
    return lx+rx;
}
void solve(){
    int n; cin>>n;
    int c=0;
	seg={0,0}; laz={0,0}; lc={0,0}; rc={0,0}; marked={0,0};
    for (int i=0; i<n; i++){
        int type,l,r; cin>>type>>l>>r;
        l+=c; r+=c;
        if (type==1){
            c=query(1,1,1e9,l,r);
            cout<<c<<'\n';
        } else update(1,1,1e9,l,r,1);
        //dbg(i);
        //dbgv(seg); dbgv(laz); dbgv(lc); dbgv(rc); dbgv(marked);
    }
}
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t=1;
//	cin>>t;
	while (t--) solve();
}

• Subtask 1: 100 / 100