oj.uz

Submission #754340

# Submission time Handle Problem Language Result Execution time Memory
754340 2023-06-07T14:07:35 Z dsyz Addk (eJOI21_addk) C++17
100 / 100
 201 ms 12616 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (100005)
ll N,K;
struct fenwick {
	ll fw[MAXN], fw2[MAXN];
	fenwick() {
		memset(fw,0,sizeof(fw));
		memset(fw2,0,sizeof(fw2));
	}
	void update(ll x,ll y,ll v){
		y++;
		for(ll tx = x;tx <= N;tx += tx&(-tx)) fw[tx] += v,fw2[tx] -= v * (x - 1);
		for(ll ty = y;ty <= N;ty += ty&(-ty)) fw[ty] -= v,fw2[ty] += v * (y - 1);
	}
	long long sum(long long x){
		ll ans = 0;
		for(ll tx = x;tx;tx -= tx&(-tx)){
			ans += (fw[tx] * x) + fw2[tx];
		}
		return ans;
	}
	long long range_sum(long long x,long long y){
		return sum(y) - sum(x - 1);
	}
} front, middle, back;
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	//note that everything is 1-indexed
	cin>>N>>K;
	ll arr[N + 1];
	for(ll i = 1;i <= N;i++){
		cin>>arr[i];
	}
	arr[0] = 0;
	ll pre[N + 1], suf[N + 1];
	memset(pre,0,sizeof(pre));
	memset(suf,0,sizeof(suf));
	for(ll i = 1;i <= N;i++){
		pre[i] = arr[i] * i;
	}
	for(ll i = N;i >= 1;i--){
		suf[i] = (arr[i] * (N - i + 1));
	}
	for(ll i = 1;i <= N;i++){
		front.update(i,i,pre[i]);
		middle.update(i,i,arr[i]);
		back.update(i,i,suf[i]);
	}
	ll Q;
	cin>>Q;
	for(ll q = 0;q < Q;q++){
		ll t;
		cin>>t;
		if(t == 1){ //1-indexed
			ll index[K];
			for(ll i = 0;i < K;i++){
				cin>>index[i];
			}
			for(ll i = 0;i < K - 1;i++){
				front.update(index[i],index[i],index[i] * -arr[index[i]] + index[i] * arr[index[i + 1]]);
				back.update(index[i],index[i],(N - index[i] + 1) * -arr[index[i]] + (N - index[i] + 1) * arr[index[i + 1]]);
				middle.update(index[i],index[i],arr[index[i + 1]] - arr[index[i]]);
			}
			front.update(index[K - 1],index[K - 1],index[K - 1] * -arr[index[K - 1]] + index[K - 1] * arr[index[0]]);
			back.update(index[K - 1],index[K - 1],(N - index[K - 1] + 1) * -arr[index[K - 1]] + (N - index[K - 1] + 1) * arr[index[0]]);
			middle.update(index[K - 1],index[K - 1],arr[index[0]] - arr[index[K - 1]]);
			ll first = arr[index[0]];
			for(ll i = 1;i < K;i++){
				arr[index[i - 1]] = arr[index[i]];
				pre[index[i - 1]] = index[i - 1] * arr[index[i - 1]];
				suf[index[i - 1]] = (N - index[i - 1] + 1) * arr[index[i - 1]];
			}
			arr[index[K - 1]] = first;
			pre[index[K - 1]] = index[K - 1] * arr[index[K - 1]];
			suf[index[K - 1]] = (N - index[K - 1] + 1) * arr[index[K - 1]];
		}else if(t == 2){ //1-indexed
			ll l,r,m;
			cin>>l>>r>>m;
			ll sum1 = 0, sum2 = 0,sum3 = 0;
			if((r - l + 1) - m > 0) sum1 += front.range_sum(l,l + ((r - l + 1) - m) - 1) - (l - 1) * middle.range_sum(l,l + ((r - l + 1) - m) - 1);
			if((r - l + 1) - m > 0) sum3 += back.range_sum(r - ((r - l + 1) - m) + 1,r) - (N - r) * middle.range_sum(r - ((r - l + 1) - m) + 1,r);
			sum2 += ((r - l + 1) - m + 1) * middle.range_sum(l + ((r - l + 1) - m),r - ((r - l + 1) - m));
			cout<<sum1 + sum2 + sum3<<'\n';
		}
	}
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5032 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 6 ms 5076 KB Output is correct
5 Correct 5 ms 5204 KB Output is correct
6 Correct 5 ms 5292 KB Output is correct
7 Correct 6 ms 5292 KB Output is correct
8 Correct 7 ms 5332 KB Output is correct
9 Correct 8 ms 5588 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6228 KB Output is correct
2 Correct 23 ms 6736 KB Output is correct
3 Correct 29 ms 7484 KB Output is correct
4 Correct 52 ms 9356 KB Output is correct
5 Correct 93 ms 11236 KB Output is correct
6 Correct 78 ms 11080 KB Output is correct
7 Correct 85 ms 10996 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 8584 KB Output is correct
2 Correct 98 ms 10472 KB Output is correct
3 Correct 201 ms 12616 KB Output is correct
4 Correct 107 ms 11536 KB Output is correct