Submission #602540

#	Time	Username	Problem	Language	Result	Execution time	Memory
602540		dozer	Addk (eJOI21_addk)	C++14	100 / 100	120 ms	8800 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define pb push_back
#define pii pair<int, int>
#define endl "\n"
#define sp " "
#define st first
#define nd second
#define N 100005
#define modulo 1000000007
#define int long long

int pre[N], suf[N], tree[N], arr[N], n;

void update(int x, int val, int bit[])
{
	while(x <= n)
	{
		bit[x] += val;
		int lsb = x & -x;
		x += lsb;
	}
}

int find(int x, int bit[])
{
	int ans = 0;
	while(x > 0)
	{
		ans += bit[x];
		int lsb = x & -x;
		x -= lsb;
	}
	return ans;
}

int32_t main()
{
	fastio();

	int k;
	cin>>n>>k;
	for (int i = 1; i <= n; i++)
		cin>>arr[i];

	for (int i = 1; i <= n; i++)
	{
		update(i, arr[i], tree);
		update(i, arr[i] * i, pre);
	}
	for (int i = n; i > 0; i--)
		update(i, (n - i + 1) * arr[i], suf);

	int q;
	cin>>q;
	while(q--)
	{
		int type;
		cin>>type;
		if (type == 1)
		{
			vector<int> inds;
			for (int i = 1; i <= k; i++)
			{
				int j;
				cin>>j;
				inds.pb(j);
			}
			int last = arr[inds[0]];
			for (int i = 1; i < k; i++)
			{
				int diff = arr[inds[i]] - arr[inds[i - 1]];
				int j = inds[i - 1];
				update(j, diff, tree);
				update(j, diff * j, pre);
				update(j, diff * (n - j + 1), suf);
				arr[inds[i - 1]] = arr[inds[i]];
			}
			int diff = last - arr[inds[k - 1]];
			arr[inds[k - 1]] = last;
			int j = inds[k - 1];
			update(j, diff, tree);
			update(j, diff * j, pre);
			update(j, diff * (n - j + 1), suf);
		}
		else
		{
			int l, r, m;
			cin>>l>>r>>m;
			int sz = r - l + 1;
			int maks = min(m, sz - m + 1);
			int a = l + maks - 1, b = r - maks + 1;
			int ans = 0;
			ans += find(a - 1, pre) - find(l - 1, pre);
			ans -= (find(a - 1, tree) - find(l - 1, tree)) * (l - 1);
			//cout<<ans<<sp;
			ans += find(r, suf) - find(b, suf);
			ans -= (find(r, tree) - find(b, tree)) * (n - r);
			//cout<<ans<<sp;
			ans += (find(b, tree) - find(a - 1, tree)) * maks;
			cout<<ans<<endl; 
		}
	}


	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

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