oj.uz

Submission #478971

# Submission time Handle Problem Language Result Execution time Memory
478971 2021-10-09T09:25:10 Z vato_chachanidze Addk (eJOI21_addk) C++14
92 / 100
 316 ms 7356 KB 
#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.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 6 ms 332 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 13 ms 572 KB Output is correct
6 Correct 14 ms 616 KB Output is correct
7 Correct 18 ms 716 KB Output is correct
8 Correct 19 ms 744 KB Output is correct
9 Correct 28 ms 972 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 1628 KB Output is correct
2 Correct 103 ms 2356 KB Output is correct
3 Correct 110 ms 3036 KB Output is correct
4 Correct 220 ms 5244 KB Output is correct
5 Correct 274 ms 7356 KB Output is correct
6 Correct 299 ms 7068 KB Output is correct
7 Correct 316 ms 7112 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 3088 KB Output isn't correct
2 Halted 0 ms 0 KB -