Submission #961139

#	Time	Username	Problem	Language	Result	Execution time	Memory
961139		MilosMilutinovic	Addk (eJOI21_addk)	C++14	100 / 100	181 ms	12624 KiB

Main

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,k,q;
int a[100005],b[100005],ids[15];
ll sum[800005][3];

void build(int id,int l,int r){
	if(l==r){
		sum[id][0]=a[l];
		sum[id][1]=a[l]*1ll*l;
		sum[id][2]=a[l]*1ll*(n-l+1);
		return;
	}
	int mid=(l+r)/2;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	sum[id][0]=sum[id<<1][0]+sum[id<<1|1][0];
	sum[id][1]=sum[id<<1][1]+sum[id<<1|1][1];
	sum[id][2]=sum[id<<1][2]+sum[id<<1|1][2];
}

ll query(int id,int l,int r,int ql,int qr,int t){
	if(ql<=l&&r<=qr) return sum[id][t];
	int mid=(l+r)/2;
	if(qr<=mid) return query(id<<1,l,mid,ql,qr,t);
	else if(ql>mid) return query(id<<1|1,mid+1,r,ql,qr,t);
	else return query(id<<1,l,mid,ql,qr,t)+query(id<<1|1,mid+1,r,ql,qr,t);
}

void change(int id,int l,int r,int p){
	if(l==r){
		sum[id][0]=a[l];
		sum[id][1]=a[l]*1ll*l;
		sum[id][2]=a[l]*1ll*(n-l+1);
		return;
	}
	int mid=(l+r)/2;
	if(p<=mid) change(id<<1,l,mid,p);
	else change(id<<1|1,mid+1,r,p);
	sum[id][0]=sum[id<<1][0]+sum[id<<1|1][0];
	sum[id][1]=sum[id<<1][1]+sum[id<<1|1][1];
	sum[id][2]=sum[id<<1][2]+sum[id<<1|1][2];
}

int main(){
	n=readint(); k=readint();
	for(int i=1;i<=n;i++) a[i]=readint();
	build(1,1,n);
	q=readint();
	while(q--){
		int op=readint();
		if(op==1){
			for(int i=1;i<=k;i++) ids[i]=readint();
			for(int i=1;i<=k;i++) b[ids[i]]=a[ids[i]];
			for(int i=1;i<=k;i++){
				a[ids[i]]=b[ids[(i%k)+1]];
				change(1,1,n,ids[i]);
			}
		}else{
			int l=readint(),r=readint(),m=readint();
			ll res=0;
			int low=l,high=r-m+1,p=l;
			while(low<=high){
				int mid=(low+high)/2;
				if(min({mid-l+1,m})==mid-l+1) p=mid,low=mid+1;
				else high=mid-1;
			}
			res+=query(1,1,n,l,p,1)-query(1,1,n,l,p,0)*(l-1);
			low=p+1,high=r;
			int q=-1;
			while(low<=high){
				int mid=(low+high)/2;
				if(min({r-mid+1,m,min(mid,r-m+1)-l+1})==r-mid+1) q=mid,high=mid-1;
				else low=mid+1;
			}
			if(p<q) res+=query(1,1,n,q,r,2)-query(1,1,n,q,r,0)*(n-r);
			if(p+1<q) res+=query(1,1,n,p+1,q-1,0)*min(m,(r-l+1)-m+1);
			printf("%lld\n",res);
		}
	}
	return 0;
}

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