Submission #645909

#	Time	Username	Problem	Language	Result	Execution time	Memory
645909		Koful123	Addk (eJOI21_addk)	C++17	0 / 100	57 ms	5460 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define mod 998244353
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

struct Fenwick{	
	int n;
	vector<int> fw,a;
	Fenwick(int _n){
		fw.assign(n = _n + 5,0);
		a.assign(n,0);
	};
	void upd(int pos,int val){
		a[pos] += val;
		while(pos < n){
			fw[pos] += val;
			pos += (pos & -pos);
		}
	}
	int get(int pos){
		int res = 0;
		while(pos > 0){
			res += fw[pos];
			pos -= (pos & -pos);
		}
		return res;
	}
	int get(int l,int r){
		if(l > r) return 0;
		return get(r) - get(l-1);
	}
};

void solve(){

	int n,k;
	cin >> n >> k;

	vector<int> v(n+1);
	for(int i=1;i<=n;i++){
		cin >> v[i];
	}

	Fenwick cum(n),pref(n),revcum(n);
	for(int i=1;i<=n;i++){
		pref.upd(i,v[i]),cum.upd(i,v[i]*i);
	}

	for(int i=n;i>=1;i--){
		revcum.upd(i,v[i]*(n-i+1));
	}

	int q; cin >> q;
	for(int i=0;i<q;i++){
		int ty; cin >> ty;
		if(ty == 1){
			vector<int> poses(k);
			for(int j=0;j<k;j++){
				cin >> poses[j];
			}
			int f = v[poses[0]];
			for(int i=0;i+1<k;i++){
				pref.upd(poses[i],v[poses[i+1]] - v[poses[i]]);
				cum.upd(poses[i],v[poses[i+1]]*poses[i] - v[poses[i]]*poses[i]);
				revcum.upd(poses[i],v[poses[i+1]]*(n-poses[i]+1) - v[poses[i]]*(n-poses[i]+1));
				v[poses[i]] = v[poses[i+1]];
			}
			v[poses[k-1]] = f;
		}
		else{
			int l,r,m; cin >> l >> r >> m;
			int rng = r - l + 1;
			if(rng < 2*m){
				int right = revcum.get(r-m+1+(2*m-rng-1),r) - pref.get(r-m+1+(2*m-rng-1),r) * (n-r);
				int sub = cum.get((l+m-1) - (2*m-1-rng) + 1,l+m-1) - pref.get((l+m-1) - (2*m-1-rng) + 1,l+m-1) * (l-1);
				int left = cum.get(l,l+m-1) - pref.get(l,l+m-1) * (l-1) - sub;
				cout << right + left << endl;
			}
			else{
				int right = revcum.get(r-m+1,r) - pref.get(r-m+1,r) * (n-r);
				int mid = pref.get(l+m,r-m) * m;
				int left = cum.get(l,l+m-1) - pref.get(l,l+m-1) * (l-1);
				cout << right + mid + left << endl;
			}
		}
	}
}

signed main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	int t = 1;
//	cin >> t;

	while(t--)
		solve();

	return 0;
}

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