Submission #1175789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175789		bahaktl	Addk (eJOI21_addk)	C++20	100 / 100	1352 ms	4788 KiB

Main

#include <bits/stdc++.h>   
using namespace std;
#define int long long
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const int inf=1e16;
const int N=2e5+10;
const int mod=1e9+7;
int t[N*4],a[N];

void update(int v,int tl,int tr,int pos) {
	if(tl==tr) {
		t[v]=a[tl];
		return;
	}
	int m=(tl+tr)/2;
	if(pos<=m) update(v*2,tl,m,pos);
	else update(v*2+1,m+1,tr,pos);
	t[v]=t[v*2]+t[v*2+1];
}

int get(int v,int tl,int tr,int l,int r) {
	if(tl>=l && tr<=r) return t[v];
	if(l>tr || r<tl) return 0;
	int m=(tl+tr)/2;
	return get(v*2,tl,m,l,r)+get(v*2+1,m+1,tr,l,r);
}

signed main () {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		update(1,1,n,i);
	}
	int q;
	cin>>q;
	while(q--) {
		int type;
		cin>>type;
		if(type==1) {
			int pos[k+1],val[k+1];
			for(int i=1;i<=k;i++) {
				int x;
				cin>>x;
				pos[i]=x;
				val[i]=a[x];
			}
			for(int i=1;i<=k;i++) {
				if(i==k) a[pos[i]]=val[1];
				else a[pos[i]]=val[i+1];
				update(1,1,n,pos[i]);
			}
		}
		else {
			int l,r,m;
			cin>>l>>r>>m;
			int ans=get(1,1,n,l,r)*m;
			for(int i=l,x=m-1;x>0;i++,x--) ans-=a[i]*x;
			for(int i=r,x=m-1;x>0;i--,x--) ans-=a[i]*x;
			cout<<ans<<"\n";
		}
	}
}   

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