oj.uz

Submission #475550

# Submission time Handle Problem Language Result Execution time Memory
475550 2021-09-22T21:50:20 Z NachoLibre Addk (eJOI21_addk) C++17
100 / 100
 138 ms 4968 KB 
#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.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 4 ms 588 KB Output is correct
8 Correct 5 ms 588 KB Output is correct
9 Correct 7 ms 756 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1228 KB Output is correct
2 Correct 21 ms 1648 KB Output is correct
3 Correct 28 ms 2104 KB Output is correct
4 Correct 48 ms 3536 KB Output is correct
5 Correct 69 ms 4968 KB Output is correct
6 Correct 69 ms 4804 KB Output is correct
7 Correct 65 ms 4724 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2264 KB Output is correct
2 Correct 79 ms 3900 KB Output is correct
3 Correct 138 ms 4160 KB Output is correct
4 Correct 77 ms 4836 KB Output is correct