Submission #1308390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308390		Jawad_Akbar_JJ	Addk (eJOI21_addk)	C++20	100 / 100	386 ms	9024 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];

struct node{
	int sz = 0, as = 0, ds = 0, sm = 0;
} seg[N<<1];

node merge(node A, node B){
	node ans;
	ans.sz = A.sz + B.sz;
	ans.sm = A.sm + B.sm;
	ans.as = A.as + B.as + B.sm * A.sz;
	ans.ds = A.ds + B.ds + A.sm * B.sz;
	return ans;
}

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){
		seg[cur].as = seg[cur].ds = seg[cur].sm = v;
		seg[cur].sz = 1;
		return;
	}
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	insert(i, v, lc, st, mid);
	insert(i, v, rc, mid, en);

	seg[cur] = merge(seg[lc], seg[rc]);
}

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


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]), a[ind[j]] = vec[j];
		}
		else{
			cin>>l>>r>>m;
			int s = min(m - 1, r - l + 1 - m);
			cout<<get(l, l + s).as + get(r - s + 1, r + 1).ds + get(l + s, r - s + 1).sm * (s + 1)<<endl;
		}
	}
}

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