oj.uz

Submission #645917

# Submission time Handle Problem Language Result Execution time Memory
645917 2022-09-28T09:30:12 Z Koful123 Addk (eJOI21_addk) C++17
92 / 100
 65 ms 9804 KB 
#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 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]];
			}
			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;
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 3 ms 624 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 4 ms 852 KB Output is correct
8 Correct 5 ms 876 KB Output is correct
9 Correct 6 ms 1128 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1664 KB Output is correct
2 Correct 20 ms 3084 KB Output is correct
3 Correct 25 ms 3988 KB Output is correct
4 Correct 42 ms 6908 KB Output is correct
5 Correct 63 ms 9804 KB Output is correct
6 Correct 65 ms 9456 KB Output is correct
7 Correct 62 ms 9524 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 3472 KB Output isn't correct
2 Halted 0 ms 0 KB -