Submission #1308386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308386		Jawad_Akbar_JJ	Addk (eJOI21_addk)	C++20	0 / 100	110 ms	3760 KiB

Main

#include <iostream>

using namespace std;
#define int long long
const int N = (1<<17) + 1;
int sm[N<<1], as[N<<1], ds[N<<1], a[N], vec[11], ind[11];

void insert(int i, int v, int cur = 1, int st = 1, int en = N){
	if (i >= en or i < st)
		return;
	if (en - st == 1){
		as[cur] = ds[cur] = sm[cur] = v;
		return;
	}
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	insert(i, v, lc, st, mid);
	insert(i, v, rc, mid, en);

	sm[cur] = sm[lc] + sm[rc];
	as[cur] = as[lc] + as[rc] + sm[rc] * (mid - st);
	ds[cur] = ds[lc] + ds[rc] + sm[lc] * (en - mid);
}

int get1(int l, int r, int cur = 1, int st = 1, int en = N){
	if (l >= en or r <= st)
		return 0;
	if (l <= st and r >= en)
		return sm[cur];
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	return get1(l, r, lc, st, mid) + get1(l, r, rc, mid, en);
}

pair<int, int> get2(int l, int r, int cur = 1, int st = 1, int en = N){
	if (l >= en or r <= st)
		return {0, 0};
	if (l <= st and r >= en)
		return {as[cur], sm[cur]};

	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	auto [A, As] = get2(l, r, lc, st, mid);
	auto [B, Bs] = get2(l, r, rc, mid, en);

	return {A + B + Bs * max(mid - l, 0LL), As + Bs};
}

pair<int, int> get3(int l, int r, int cur = 1, int st = 1, int en = N){
	if (l >= en or r <= st)
		return {0, 0};
	if (l <= st and r >= en)
		return {ds[cur], sm[cur]};

	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	auto [A, As] = get3(l, r, lc, st, mid);
	auto [B, Bs] = get3(l, r, rc, mid, en);

	return {A + B + As * max(r - mid, 0LL), As + Bs};
}



signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, k, q;
	cin>>n>>k;

	for (int i=1;i<=n;i++)
		cin>>a[i], insert(i, a[i]);

	cin>>q;
	for (int i=1;i<=q;i++){
		int t, l, r, m;
		cin>>t;
		if (t == 1){
			for (int j=1;j<=k;j++)
				cin>>ind[j], vec[j-1] = a[ind[j]];
			vec[k] = a[ind[1]];

			for (int j=1;j<=k;j++)
				insert(ind[j], vec[j]);
		}
		else{
			cin>>l>>r>>m;
			int s = min(m - 1, r - l + 1 - m);
			cout<<get2(l, l + s).first + get3(r - s+1, r + 1).first + get1(l + s, r - s + 1) * (s + 1)<<endl;
		}
	}
}

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