Submission #475455

#	Time	Username	Problem	Language	Result	Execution time	Memory
475455		GioChkhaidze	Addk (eJOI21_addk)	C++14	100 / 100	161 ms	7736 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int N = 1e5 + 5;

int n, k, q, typ;
int a[N], b[N], c[N], A[N];
ll G[2 * N][4];

void upd(int x, ll dl) {
	while (x <= 100000) {
		G[x][typ] += dl;
		x += (x & -x);
	}
}

ll get(int x) {
	ll res = 0;
	while (x > 0) {
		res += G[x][typ];
		x -= (x & -x);
	}
	return res;
}

main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		typ = 0, upd(i, a[i]);
		typ = 1, upd(i, 1ll * a[i] * i);
	}
	
	cin >> q;
	for (int i = 1; i <= q; ++i) {
		int t;
		cin >> t;
		if (t == 1) {
			for (int j = 0; j < k; ++j) {
				cin >> b[j];
				A[b[j]] = a[b[j]];
			}
			
			for (int j = 0; j < k; ++j) {
				int id = b[j], idn = b[(j + 1) % k];
				typ = 0, upd(id, -a[id]);
				typ = 1, upd(id, -a[id] * id);
				a[b[j]] = A[idn];
				typ = 1, upd(id, a[id] * id);
				typ = 0, upd(id, a[id]);
			}
		}
			else
		if (t == 2) {
			int l, r, m;
			cin >> l >> r >> m;
			int L = min(l + m - 1, r - m + 1);
			int R = max(l + m - 1, r - m + 1);
			int M = L - l + 1;
			
			ll ansL = 0, ansM = 0, ansR = 0;
			
			if (L <= R) {
				typ = 0, ansM = (get(R) - get(L - 1)) * M; // correct
			}
			
			typ = 1, ansL = get(L - 1) - get(l - 1);
			typ = 0, ansL -= (get(L - 1) - get(l - 1)) * (l - 1); // correct
			
			typ = 0, ansR = (get(r) - get(R)) * (r + 1); // correct
			typ = 1, ansR -= get(r) - get(R);
			
			/*
			cout << L << " "  << M << " " << R << "\n";
			cout << ansL << " " << ansM << " " << ansR << "\n";
			*/
			cout << ansL + ansM + ansR << "\n";
		}
	}
	
	return 0;
}

Compilation message (stderr)

Main.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   28 | main() {
      | ^~~~

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