Submission #483030

#	Time	Username	Problem	Language	Result	Execution time	Memory
483030		vato_chachanidze	Addk (eJOI21_addk)	C++14	100 / 100	366 ms	8716 KiB

Main

#include<bits/stdc++.h>
using namespace std;
long long n,k,a[100009],pref[100009],pref2[100009],pref3[100009],type,l,r,m,siz,z,cnt,shes[100];
void update(long long ind,long long maxind,long long a,long long b,long long fenvik[])
{
	while(ind<=maxind)
	{
		fenvik[ind]+=a-b;
		ind+=(ind & -ind); 
	}
}
long long findans(long long ind,long long maxind,long long fenvik[])
{
	long long sum=0;
	while(ind>0)
	{
		sum+=fenvik[ind];
		ind-=(ind & -ind);	
	}
	return sum;
}
int main()
{
	cin>>n>>z;
	for(k=1;k<=n;k++)
	{
		cin>>a[k];
	}
	for(k=1;k<=n;k++)
	{
		//pref[k]=pref[k-1]+a[k];
		//pref2[k]=pref2[k-1]+a[k]*k;
		update(k,n,a[k],0,pref);
		update(k,n,a[k]*k,0,pref2);
	}
	for(k=n;k>=1;k--)
	{
		//pref3[k]=pref3[k+1]+a[k]*(n-k+1);
		update(k,n,a[k]*(n-k+1),0,pref3);
	}
	int q;
	cin>>q;
	while(q--)
	{
		cin>>type;
		if(type==2)
		{
			cin>>l>>r>>m;
			long long ans1,ans2,ans3;
			if(r-l+1>=m*2)
			{
				//ans1=pref2[l+m-2]-pref2[l-1];
				//ans1-=(pref[l+m-2]-pref[l-1])*(l-1);
				ans1=findans(l+m-2,n,pref2)-findans(l-1,n,pref2);
				ans1-=(findans(l+m-2,n,pref)-findans(l-1,n,pref))*(l-1);
				
				//ans2=pref3[r-m+2]-pref3[r+1];
				//ans2-=(pref[r]-pref[r-m+1])*(n-r);
				//ans2=(findans(n,n,pref3)-findans(r-m+1,n,pref3))-(findans(n,n,pref3)-findans(r,n,pref3));
				
				ans2=findans(r,n,pref3)-findans(r-m+1,m,pref3);
				ans2-=(findans(r,n,pref)-findans(r-m+1,n,pref))*(n-r);
				
				//ans3=(pref[r-m+1]-pref[l+m-2])*m;
				ans3=(findans(r-m+1,n,pref)-findans(l+m-2,n,pref))*m;
				
				cout<<ans1+ans2+ans3<<endl;
			}
			else
			{
				if(r-l+1<m)
				{
					cout<<"0"<<endl;
					continue;
				}
				siz=r-l+1;
				cnt=siz-m+1;
				//ans1=pref2[l+cnt-2]-pref2[l-1]-(pref[l+cnt-2]-pref[l-1])*(l-1);
				ans1=findans(l+cnt-2,n,pref2)-findans(l-1,n,pref2)-(findans(l+cnt-2,n,pref)-findans(l-1,n,pref))*(l-1);
				
				//ans2=pref3[r-cnt+2]-pref3[r+1]-(pref[r]-pref[r-cnt+1])*(n-r);
				//ans2=(findans(n,n,pref3)-findans(r-cnt+1,n,pref3))-(findans(n,n,pref3)-findans(r,n,pref3))-(findans(r,n,pref)-findans(r-cnt+1,n,pref))*(n-r);
				ans2=findans(r,n,pref3)-findans(r-cnt+1,n,pref3)-(findans(r,n,pref)-findans(r-cnt+1,n,pref))*(n-r);
				
				//ans3=(pref[r-cnt+1]-pref[l+cnt-2])*cnt;
				ans3=(findans(r-cnt+1,n,pref)-findans(l+cnt-2,n,pref))*cnt;
				
				cout<<ans1+ans2+ans3<<endl;
			}
		}
		else
		{
			for(int i=1;i<=z;i++)
			{
				cin>>shes[i];
			}
			for(int i=1;i<=z-1;i++)
			{
				update(shes[i],n,a[shes[i+1]],a[shes[i]],pref);
				update(shes[i],n,a[shes[i+1]]*shes[i],a[shes[i]]*shes[i],pref2);
				update(shes[i],n,a[shes[i+1]]*(n-shes[i]+1),a[shes[i]]*(n-shes[i]+1),pref3);
			}
			
			update(shes[z],n,a[shes[1]],a[shes[z]],pref);
			update(shes[z],n,a[shes[1]]*shes[z],a[shes[z]]*shes[z],pref2);
			update(shes[z],n,a[shes[1]]*(n-shes[z]+1),a[shes[z]]*(n-shes[z]+1),pref3);
				
			long long o=a[shes[1]];
			for(int i=1;i<=z-1;i++)
			{
				a[shes[i]]=a[shes[i+1]];
			}
			a[shes[z]]=o;
			
			
		}
	}
}

• Subtask 1: 36 / 36
• Subtask 2: 56 / 56
• Subtask 3: 8 / 8