Submission #1219179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219179		boclobanchat	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	170 ms	63404 KiB

apple

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e6+69;
int seg[MAXN],lazy[MAXN],nex[MAXN][2],cnode=1;
void down(int pos,int l,int r)
{
	int val=lazy[pos],mid=(l+r)/2;
	if(!val) return ;
	if(!nex[pos][0]) nex[pos][0]=++cnode;
	if(!nex[pos][1]) nex[pos][1]=++cnode;
	seg[nex[pos][0]]=(val-1)*(mid-l+1);
	seg[nex[pos][1]]=(val-1)*(r-mid);
	lazy[nex[pos][0]]=lazy[nex[pos][1]]=val;
	lazy[pos]=0;
}
void update(int l,int r,int u,int v,int val,int pos)
{
	if(v<l||r<u) return ;
	if(u<=l&&r<=v)
	{
		seg[pos]=val*(r-l+1),lazy[pos]=val+1;
		return ;
	}
	int mid=(l+r)/2;
	down(pos,l,r);
	if(!nex[pos][0]) nex[pos][0]=++cnode;
	if(!nex[pos][1]) nex[pos][1]=++cnode;
	update(l,mid,u,v,val,nex[pos][0]);
	update(mid+1,r,u,v,val,nex[pos][1]);
	seg[pos]=seg[nex[pos][0]]+seg[nex[pos][1]];
}
int get(int l,int r,int u,int v,int pos)
{
	if(v<l||r<u) return 0;
	if(u<=l&&r<=v) return seg[pos];
	int mid=(l+r)/2;
	down(pos,l,r);
	if(!nex[pos][0]) nex[pos][0]=++cnode;
	if(!nex[pos][1]) nex[pos][1]=++cnode;
	return get(l,mid,u,v,nex[pos][0])+get(mid+1,r,u,v,nex[pos][1]);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int q,c=0;
    cin>>q;
    while(q--)
    {
    	int t,l,r;
    	cin>>t>>l>>r;
    	l+=c,r+=c;
    	if(t==2) update(1,1e9,l,r,1,1);
    	else cout<<(c=get(1,1e9,l,r,1))<<"\n";
	}
}

• Subtask 1: 0 / 100