Submission #479043

#	Time	Username	Problem	Language	Result	Execution time	Memory
479043		vato_chachanidze	Addk (eJOI21_addk)	C++14	0 / 100	245 ms	4144 KiB

Main

#include<bits/stdc++.h>
using namespace std;
int n,k,a[100009],pref[200009],pref2[200009],pref3[2000009],type,l,r,m,siz,z,cnt,new_n=1,fans;
int get(int a[],int l,int r,int L,int R,int ind)
{
	int x=0;
	if(l>r) return x;
	if(r<L || l>R) return x;
	if(l>=L && r<=R) return a[ind];
	return get(a,l,(l+r)/2,L,R,ind*2)+get(a,(l+r)/2+1,r,L,R,ind*2+1);
}
void update(int a[],int ind)
{
	a[ind]=a[ind*2]+a[ind*2+1];
	if(ind!=1)	update(a,ind/2);
}
int main()
{
	cin>>n>>z;
	for(k=1;k<=n;k++)
	{
		cin>>a[k];
	}
	while(new_n<n)
	{
		new_n*=2;
	}
	for(k=new_n;k<=new_n+n-1;k++)
	{
		pref[k]=a[k-new_n+1];
		pref2[k]=a[k-new_n+1]*(k-new_n+1);
		pref3[k]=a[k-new_n+1]*((new_n+n)-k);
	}
	for(k=new_n-1;k>=1;k--)
	{
		pref[k]=pref[k*2]+pref[k*2+1];
		pref2[k]=pref2[k*2]+pref2[k*2+1];
		pref3[k]=pref3[k*2]+pref3[k*2+1];
	}
	//cout<<get(pref,1,new_n,1,1,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=get(pref2,1,new_n,l,l+m-2,1);
				ans1-=get(pref,1,new_n,l,l+m-2,1)*(l-1);
				
				ans2=get(pref3,1,new_n,r-m+2,r,1);
				ans2-=get(pref,1,new_n,r-m+2,r,1)*(n-r);
				
				ans3=get(pref,1,new_n,l+m-1,r-m+1,1)*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=get(pref2,1,new_n,l,l+cnt-2,1)-get(pref,1,new_n,l,l+cnt-2,1)*(l-1);
				//ans1=pref2[l+cnt-2]-pref2[l-1]-(pref[l+cnt-2]-pref[l-1])*(l-1);
				
				ans2=get(pref3,1,new_n,r-cnt+2,r,1)-get(pref,1,new_n,r-cnt+2,r,1)*(n-r);
				//ans2=pref3[r-cnt+2]-pref3[r+1]-(pref[r]-pref[r-cnt+1])*(n-r);
				
				ans3=get(pref,1,new_n,l+cnt-1,r-cnt+1,1)*cnt;
				//ans3=(pref[r-cnt+1]-pref[l+cnt-2])*cnt;
				
				cout<<ans1+ans2+ans3<<endl;
			}
		}
		else
		{
			int x;
			vector<long long> v1,v2;
			for(int i=1;i<=z;i++)
			{
				cin>>x;
				v1.push_back(x);
				v2.push_back(a[x]);
			}
			for(int i=0;i<z-1;i++)
			{
				a[v1[i]]=v2[i+1];
				pref[v1[i]+new_n-1]=v2[i+1];
				pref2[v1[i]+new_n-1]=v2[i+1]*v1[i];
				pref3[v1[i]+new_n-1]=v2[i+1]*(n-v1[i]+1);
			}
			a[v1[z-1]]=v2[0];
			pref[v1[z-1]+new_n-1]=v2[0];
			pref2[v1[z-1]+new_n-1]=v2[0]*v1[z-1];
			pref3[v1[z-1]+new_n-1]=v2[0]*(n-v1[z-1]+1);
			
			for(int i=0;i<v1.size();i++)
			{
				update(pref,(v1[i]+new_n-1)/2);
				update(pref2,(v1[i]+new_n-1)/2);
				update(pref3,(v1[i]+new_n-1)/2);
			}
		}
	}
}
/*

7 9 5 1 6 3 4 2

9 + 10 + 4 + 6 = 29
21

*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:105:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    for(int i=0;i<v1.size();i++)
      |                ~^~~~~~~~~~

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