Submission #915397

#	Time	Username	Problem	Language	Result	Execution time	Memory
915397		XXBabaProBerkay	Addk (eJOI21_addk)	C++17	100 / 100	224 ms	15860 KiB

Main

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

#define F first
#define S second

using ll = long long;

const int INF = 1e9 + 7;
const int MOD = 998244353;

struct node
{
	ll sz, inc, sum;
};

int N;
vector<ll> A;
vector<node> tree;

node create_node(ll x)
{
	node res;
	res.sz = (x == 0) ? 0 : 1;
	res.sum = res.inc = x;

	return res;
}

node combine(node a, node b)
{
	node res;

	res.sz = a.sz + b.sz;
	res.inc = a.inc + b.inc + b.sum * a.sz;
	res.sum = a.sum + b.sum;

	return res;
}

void build(int l = 1, int r = N, int k = 1)
{
	if (l == r)
	{
		tree[k] = create_node(A[l]);
		return;
	}

	int m = (l + r) >> 1;

	build(l, m, k << 1);
	build(m + 1, r, k << 1 | 1);

	tree[k] = combine(tree[k << 1], tree[k << 1 | 1]);
}

void update(int pos, int x, int l = 1, int r = N, int k = 1)
{
	if (l > pos || r < pos)
		return;
	if (l == r && r == pos)
	{
		tree[k] = create_node(x);
		return;
	}

	int m = (l + r) >> 1;
	
	update(pos, x, l, m, k << 1);
	update(pos, x, m + 1, r, k << 1 | 1);

	tree[k] = combine(tree[k << 1], tree[k << 1 | 1]);
}

node query(int ql, int qr, int l = 1, int r = N, int k = 1)
{
	if (l > qr || r < ql)
		return create_node(0);
	if (l >= ql && r <= qr)
		return tree[k];
	int m = (l + r) >> 1;

	return combine(query(ql, qr, l, m, k << 1), query(ql, qr, m + 1, r, k << 1 | 1));
}

ll ans(int l, int r)
{
	int mid = (l + r) >> 1;
	ll x = query(l, r).inc;
	if ((r - l + 1) & 1)
		return x - query(mid + 1, r).inc * 2;
	else
		return x - query(mid + 1, r).inc - query(mid + 2, r).inc;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int K;
	cin >> N >> K;
	A.resize(N + 1);
	tree.resize(N << 2);
	for (int i = 1; i <= N; i++)
		cin >> A[i];

	build();

	int Q;
	cin >> Q;
	while (Q--)
	{
		int q;
		cin >> q;
		if (q == 2)
		{
			int l, r, m;
			cin >> l >> r >> m;
			m = min(m, r - l + 2 - m);
			int mid = (r - l + 2) >> 1;
			if (m < mid)
				cout << ans(l, r) - ans(l + m, r - m) << '\n';
			else
				cout << ans(l, r) << '\n';
		}
		else
		{
			vector<int> v(K);
			for (int i = 0; i < K; i++)
				cin >> v[i];
			int tmp = A[v[0]];
			for (int i = 0; i < K - 1; i++)
			{
				update(v[i], A[v[i + 1]]);
				A[v[i]] = A[v[i + 1]];
			}

			update(v[K - 1], tmp);
			A[v[K - 1]] = tmp;
		}
	}
}

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