oj.uz

Submission #602540

# Submission time Handle Problem Language Result Execution time Memory
602540 2022-07-23T07:50:50 Z dozer Addk (eJOI21_addk) C++14
100 / 100
 120 ms 8800 KB 
#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.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 6 ms 980 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1748 KB Output is correct
2 Correct 21 ms 2312 KB Output is correct
3 Correct 24 ms 3064 KB Output is correct
4 Correct 50 ms 4664 KB Output is correct
5 Correct 73 ms 6104 KB Output is correct
6 Correct 65 ms 5956 KB Output is correct
7 Correct 65 ms 5864 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3492 KB Output is correct
2 Correct 60 ms 6244 KB Output is correct
3 Correct 120 ms 8800 KB Output is correct
4 Correct 74 ms 7600 KB Output is correct