Submission #640903

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
640903	2022-09-15T14:03:20 Z	alex_2008	Addk (eJOI21_addk)	C++14	92 / 100	235 ms	7344 KB

Main

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
ll pref[N], a[N], prefsum[N], suffsum[N];
int main() {
	ll n, k;
	cin >> n >> k;
	for (ll i = 1; i <= n; i++)
	{
		cin >> a[i];
		pref[i] = pref[i - 1] + a[i];
		prefsum[i] = prefsum[i - 1] + i * a[i];
 	}
	for (ll i = n; i >= 1; i--) {
		suffsum[i] = suffsum[i + 1] + (n + 1 - i) * a[i];
	}
	int q;
	cin >> q;
	while (q--) {
		int t, x;
		cin >> t;
		if (t == 1) {
			cin >> x;
		}
		else {
			ll l, r, m;
			cin >> l >> r >> m;
			if ((r - l + 1) > 2 * (m - 1)) {
				ll ans = prefsum[l + m - 2] - prefsum[l - 1] + suffsum[r - m + 2] - suffsum[r + 1];
				ans -= (l - 1) * (pref[l + m - 2] - pref[l - 1]);
				ans -= (n - r) * (pref[r] - pref[r - m + 1]);
				ans += m * (pref[r - m + 1] - pref[l + m - 2]);
				cout << ans << "\n";
			}
			else {
				ll sz = r - l + 1 - m;
				ll ans = prefsum[l + sz - 1] - prefsum[l - 1] + suffsum[r - sz + 1] - suffsum[r + 1];
				ans -= (l - 1) * (pref[l + sz - 1] - pref[l - 1]);
				ans -= (n - r) * (pref[r] - pref[r - sz]);
				ans += (sz + 1) * (pref[r - sz] - pref[l + sz - 1]);
				cout << ans << "\n";
			}
		}
	}
}

Subtask #1

36.0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	3 ms	324 KB	Output is correct
3	Correct	5 ms	404 KB	Output is correct
4	Correct	7 ms	452 KB	Output is correct
5	Correct	9 ms	588 KB	Output is correct
6	Correct	12 ms	640 KB	Output is correct
7	Correct	14 ms	724 KB	Output is correct
8	Correct	16 ms	736 KB	Output is correct
9	Correct	23 ms	928 KB	Output is correct

Subtask #2

56.0 / 56.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	1636 KB	Output is correct
2	Correct	71 ms	2380 KB	Output is correct
3	Correct	99 ms	3008 KB	Output is correct
4	Correct	170 ms	5284 KB	Output is correct
5	Correct	235 ms	7344 KB	Output is correct
6	Correct	235 ms	7112 KB	Output is correct
7	Correct	224 ms	7060 KB	Output is correct

Subtask #3

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	122 ms	4172 KB	Output isn't correct
2	Halted	0 ms	0 KB	-