Submission #1110806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110806		_rain_	Addk (eJOI21_addk)	C++14	100 / 100	202 ms	12360 KiB

Main

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
#define name "main"
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(b);i>=(a);--i)

const int N=(int)1'00'000;
int a[N+2];
int n,k,q;

#define lef(id) id<<1
#define rig(id) id<<1|1
LL st[N*4+2],lazy[N*4+2];
void pushdown(int id,int l,int r){
	int m=(l+r)>>1;
	LL &t=lazy[id];
	st[lef(id)]+=t*(m-l+1),lazy[lef(id)]+=t;
	st[rig(id)]+=t*(r-m),lazy[rig(id)]+=t;
	t=0;
	return;
}
void upd(int id,int l,int r,int u,int v,LL val){
	if (l>v||r<u) return;
	if (u<=l&&r<=v){
		st[id]+=val*(r-l+1);
		lazy[id]+=val;
		return;
	}
	int m=(l+r)>>1;
	pushdown(id,l,r);
	upd(lef(id),l,m,u,v,val);
	upd(rig(id),m+1,r,u,v,val);
	st[id]=st[lef(id)]+st[rig(id)];
}
LL Get(int id,int l,int r,int u,int v){
	if (l>v||r<u) return 0;
	if (u<=l&&r<=v) return st[id];
	int m=(l+r)>>1;
	pushdown(id,l,r);
	return Get(lef(id),l,m,u,v)+Get(rig(id),m+1,r,u,v);
}

void giai(){
	int t;cin>>t;
	if (t==1){
		vector<int>idx(k+2,0);
		vector<int>val(k+2,0);
		FOR(i,1,k) cin>>idx[i];
		idx[k+1]=idx[1];
		FOR(i,2,k+1){
			val[i-1]=a[idx[i]];
			upd(1,1,n,idx[i-1],n,a[idx[i]]-a[idx[i-1]]);
		}
		FOR(i,1,k) a[idx[i]]=val[i];
	}
	if (t==2)
	{
		int l,r,m;cin>>l>>r>>m;
		cout<<Get(1,1,n,l+m-1,r)-Get(1,1,n,l-1,r-m)<<'\n';
	}
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>k;
	FOR(i,1,n){
		cin>>a[i];
		upd(1,1,n,i,n,a[i]);
	}
	cin>>q;
	while(q--) giai();
	exit(0);
}

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