Submission #478971

#	Time	Username	Problem	Language	Result	Execution time	Memory
478971		vato_chachanidze	Addk (eJOI21_addk)	C++14	92 / 100	316 ms	7356 KiB

Main

#include<bits/stdc++.h>
using namespace std;
long long n,k,a[100009],pref[1000009],pref2[100009],pref3[1000009],type,l,r,m,siz,z,cnt;
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;
	}
	for(k=n;k>=1;k--)
	{
		pref3[k]=pref3[k+1]+a[k]*(n-k+1);
	}
	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);
				
				ans2=pref3[r-m+2]-pref3[r+1];
				ans2-=(pref[r]-pref[r-m+1])*(n-r);
				
				ans3=(pref[r-m+1]-pref[l+m-2])*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);
				ans2=pref3[r-cnt+2]-pref3[r+1]-(pref[r]-pref[r-cnt+1])*(n-r);
				ans3=(pref[r-cnt+1]-pref[l+cnt-2])*cnt;
				
				cout<<ans1+ans2+ans3<<endl;
			}
		}
		else
		{
			long long q;
			cin>>q;
		}
	}
}
/*

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