oj.uz

Submission #645954

# Submission time Handle Problem Language Result Execution time Memory
645954 2022-09-28T10:47:35 Z Koful123 Addk (eJOI21_addk) C++17
100 / 100
 140 ms 11084 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]],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

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.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 532 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 4 ms 840 KB Output is correct
8 Correct 5 ms 852 KB Output is correct
9 Correct 7 ms 1180 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2124 KB Output is correct
2 Correct 19 ms 3072 KB Output is correct
3 Correct 25 ms 4080 KB Output is correct
4 Correct 43 ms 6860 KB Output is correct
5 Correct 75 ms 9096 KB Output is correct
6 Correct 71 ms 8924 KB Output is correct
7 Correct 80 ms 8832 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 4684 KB Output is correct
2 Correct 69 ms 8260 KB Output is correct
3 Correct 140 ms 11084 KB Output is correct
4 Correct 72 ms 10040 KB Output is correct