Submission #774776

#	Time	Username	Problem	Language	Result	Execution time	Memory
774776		vjudge1	Addk (eJOI21_addk)	C++17	100 / 100	81 ms	5216 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int NM = 1e6, KM = 10;

int N, K, Q, a[NM+5];
int bit[NM+5], bit2[NM+5];
int idx[KM+5], b[NM+5];

void update(int bit[NM+5], int p, int v){
	while (p <= N){
		bit[p] += v;
		p += p & (-p);
	}
}

int get(int bit[NM+5], int p){
	int res = 0;
	while (p > 0){
		res += bit[p];
		p -= p & (-p);
	}
	return res;
}

void modify(){
	for (int i = 1; i < K; i++)
		b[idx[i]] = a[idx[i+1]];
	b[idx[K]] = a[idx[1]];
	for (int i = 1; i <= K; i++){
		update(bit, idx[i], b[idx[i]]-a[idx[i]]);
		update(bit2, idx[i], (b[idx[i]]-a[idx[i]])*idx[i]);
		a[idx[i]] = b[idx[i]];
	}
}

int get(int l, int r){
	return get(bit, r)-get(bit, l-1);
}

int get1(int l, int r){
	return get(bit2, r)-get(bit2, l-1)-(l-1)*get(l, r);
}

int get2(int l, int r){
	return -get1(l, r)+(r-l+2)*get(l, r);
}

void query(int l, int r, int m){
	int t = min(m, r-l-m+2);
	cout << get1(l, l+t-2)+get(l+t-1, r-t+1)*t+get2(r-t+2, r) << '\n';
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= N; i++){
		cin >> a[i];
		update(bit, i, a[i]);
		update(bit2, i, a[i]*i);
	}
	cin >> Q;
	while (Q--){
		int type; cin >> type;
		if (type == 1){
			for (int i = 1; i <= K; i++) cin >> idx[i];
			modify();
		}
		else{
			int l, r, m;
			cin >> l >> r >> m;
			query(l, r, m);
		}
	}
	return 0;
}

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