oj.uz

답안 #483012

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
483012 2021-10-27T11:56:55 Z vato_chachanidze Addk (eJOI21_addk) C++14
0 / 100
 51 ms 2240 KB 
#include<bits/stdc++.h>
using namespace std;
int n,k,a[100009],pref[1000009],pref2[100009],pref3[1000009],type,l,r,m,siz,z,cnt;
void update(int ind,int maxind,int a,int b,int fenvik[])
{
	while(ind<=maxind)
	{
		fenvik[ind]+=a-b;
		ind+=(ind & -ind); 
	}
}
int findans(int ind,int maxind,int fenvik[])
{
	int 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,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);
				
				//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 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
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Incorrect 5 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 1260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 51 ms 2240 KB Output isn't correct
2 Halted 0 ms 0 KB -