Submission #475550

#	Time	Username	Problem	Language	Result	Execution time	Memory
475550		NachoLibre	Addk (eJOI21_addk)	C++17	100 / 100	138 ms	4968 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define sz(x) ((int)x.size())
using namespace std;

struct order {
	order(int _n) {
		f[0].resize(_n + 1);
		f[1].resize(_n + 1);
		x[0].resize(_n + 1);
		x[1].resize(_n + 1);
	}

private:
	vector<long long> x[2], f[2];
	void add(int i, long long y, int z) {
		x[z][i] += y;
		while(i < sz(f[z])) {
			f[z][i] += y;
			i += i & -i;
		}
	}
	long long psum(int r, int z) {
		long long x = 0;
		while(r > 0) {
			x += f[z][r];
			r -= r & -r;
		}
		return x;
	}
	long long sum(int l, int r) {
		if(l > r) return 0;
		return psum(r, 0) - psum(l - 1, 0);
	}
	long long inc(int l, int r, long long y) {
		if(l > r) return 0;
		return psum(r, 1) - psum(l - 1, 1) + sum(l, r) * (y - l);
	}
	void turn(int i, int j) {
		long long y = x[0][j];
		set(j, x[0][i]);
		set(i, y);
	}
public:
	void set(int i, long long y) {
		add(i, y - x[0][i], 0);
		add(i, y * i - x[1][i], 1);
	}
	void turn(vector<int> v) {
		for(int i = 1; i < sz(v); ++i) {
			turn(v[i], v[i - 1]);
		}
	}
	long long answer(int l, int r, int m) {
		return inc(l, r - m + 1, l + 1)
		     + sum(r - m + 2, r) * (r - m + 2)
		     - sum(l, l + m - 1) * l
			 - inc(l + m, r, l + 1);
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	order o(n);
	for(int i = 1; i <= n; ++i) {
		int a;
		cin >> a;
		o.set(i, a);
	}
	int q;
	cin >> q;
	for(int i = 0; i < q; ++i) {
		int qt;
		cin >> qt;
		if(qt == 1) {
			vector<int> v(k);
			for(int i = 0; i < k; ++i) {
				cin >> v[i];
			}
			o.turn(v);
		} else {
			int l, r, m;
			cin >> l >> r >> m;
			cout << o.answer(l, r, m) << "\n";
		}
	}
	return 0;
}

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