Submission #645954

#	Time	Username	Problem	Language	Result	Execution time	Memory
645954		Koful123	Addk (eJOI21_addk)	C++17	100 / 100	140 ms	11084 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]],s = poses[0];
			for(int j=0;j+1<k;j++){
				pref.upd(poses[j],v[poses[j+1]] - v[poses[j]]);
				cum.upd(poses[j],v[poses[j+1]]*poses[j] - v[poses[j]]*poses[j]);
				revcum.upd(poses[j],v[poses[j+1]]*(n-poses[j]+1) - v[poses[j]]*(n-poses[j]+1));
				v[poses[j]] = v[poses[j+1]];
			}
			pref.upd(poses[k-1],f - v[poses[k-1]]);
			cum.upd(poses[k-1],f*poses[k-1] - v[poses[k-1]]*poses[k-1]);
			revcum.upd(poses[k-1],f*(n-poses[k-1]+1) - v[poses[k-1]]*(n-poses[k-1]+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),r) - pref.get(r-m+1+(2*m-rng),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+m-1) - (2*m-1-rng));
				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;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:68:24: warning: unused variable 's' [-Wunused-variable]
   68 |    int f = v[poses[0]],s = poses[0];
      |                        ^

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