oj.uz

Submission #915397

# Submission time Handle Problem Language Result Execution time Memory
915397 2024-01-23T19:49:12 Z XXBabaProBerkay Addk (eJOI21_addk) C++17
100 / 100
 224 ms 15860 KB 
#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.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 5 ms 1112 KB Output is correct
5 Correct 7 ms 960 KB Output is correct
6 Correct 8 ms 1140 KB Output is correct
7 Correct 10 ms 1116 KB Output is correct
8 Correct 12 ms 1368 KB Output is correct
9 Correct 17 ms 1628 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3160 KB Output is correct
2 Correct 55 ms 4436 KB Output is correct
3 Correct 74 ms 5968 KB Output is correct
4 Correct 136 ms 10312 KB Output is correct
5 Correct 218 ms 14832 KB Output is correct
6 Correct 183 ms 14164 KB Output is correct
7 Correct 209 ms 14284 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 7728 KB Output is correct
2 Correct 182 ms 12060 KB Output is correct
3 Correct 224 ms 15860 KB Output is correct
4 Correct 215 ms 14676 KB Output is correct