Submission #640903

#	Time	Username	Problem	Language	Result	Execution time	Memory
640903		alex_2008	Addk (eJOI21_addk)	C++14	92 / 100	235 ms	7344 KiB

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 / 36
• Subtask 2: 56 / 56
• Subtask 3: 0 / 8