Submission #483027

#	Time	Username	Problem	Language	Result	Execution time	Memory
483027		vato_chachanidze	Addk (eJOI21_addk)	C++14	92 / 100	242 ms	7428 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;
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
		{
			long long z;
			cin>>z;
		}
	}
}
/*
 
1 2 3 4
 
1 3 6 10
1 5 14 30
20 16 10 4
 
2+6
 
14 - 1 -(6-1)*(2-1)
 
 
1 2 3 4
 
2 - 4  m = 2
2 3
 
pref2[(r+l)/2] - pref2[l-1] - (pref[(r+l)/2] - pref[l-1])*(l-1)
 
 
8
7 2 5 1 9 3 4 6
3
2 2 6 2
 
2 5 1 9 3 4
2+10+3
 
iqamde gaizrdeba sanam l+m!=r
2 3 4 5 6
*/

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