oj.uz

Submission #777651

# Submission time Handle Problem Language Result Execution time Memory
777651 2023-07-09T12:14:28 Z ihceker Addk (eJOI21_addk) C++14
100 / 100
 257 ms 8640 KB 
#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

int n,k,f[100005],f2[100005],f3[100005];

void update(int x,int y){
	for(int i=x;i<=n;i+=(i&-i)){
		f[i]+=y;
	}
	return;
}

void update2(int x,int y){
	for(int i=x;i<=n;i+=(i&-i)){
		f2[i]+=y;
	}
	return;
}

void update3(int x,int y){
	for(int i=x;i>=1;i-=((n-i+1)&(i-n-1))){
		f3[i]+=y;
	}
	return;
}

int query(int x){
	int y=0;
	for(int i=x;i>=1;i-=(i&-i)){
		y+=f[i];
	}
	return y;
}

int query2(int x){
	int y=0;
	for(int i=x;i>=1;i-=(i&-i)){
		y+=f2[i];
	}
	return y;
}

int query3(int x){
	int y=0;
	for(int i=x;i<=n;i+=((n-i+1)&(i-n-1))){
		y+=f3[i];
	}
	return y;
}

int32_t main(){
	cin>>n>>k;
	int arr[n+5];
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	for(int i=1;i<=n;i++){
		update(i,arr[i]);
		update2(i,arr[i]*i);
		update3(i,arr[i]*(n-i+1));
	}
	int q;
	cin>>q;
	while(q--){
		int a;
		cin>>a;
		if(a==1){
			int b[k];
			for(int i=0;i<k;i++)cin>>b[i];
			vector<int>v;
			int x=arr[b[0]];
			for(int i=0;i<k-1;i++){
				v.pb(arr[b[i]]);
				arr[b[i]]=arr[b[i+1]];
			}
			v.pb(arr[b[k-1]]);
			arr[b[k-1]]=x;
			for(int i=0;i<k;i++){
				update(b[i],arr[b[i]]-v[i]);
				update2(b[i],(arr[b[i]]-v[i])*b[i]);
				update3(b[i],(arr[b[i]]-v[i])*(n-b[i]+1));
			}
		}
		else{
			int x,y,z;
			cin>>x>>y>>z;
			if(z==1){
				cout<<query(y)-query(x-1)<<endl;
				continue;
			}
			int l=x+z-1,r=y-z+1;
			cout<<(query(r)-query(l-1))*z+query2(l-1)-query2(x-1)-(query(l-1)-query(x-1))*(x-1)+query3(r+1)-query3(y+1)-(query(y)-query(r))*(n-y)<<endl;
		}
	}
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 7 ms 388 KB Output is correct
5 Correct 8 ms 468 KB Output is correct
6 Correct 11 ms 576 KB Output is correct
7 Correct 13 ms 696 KB Output is correct
8 Correct 14 ms 704 KB Output is correct
9 Correct 27 ms 896 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 1612 KB Output is correct
2 Correct 61 ms 2288 KB Output is correct
3 Correct 82 ms 3000 KB Output is correct
4 Correct 146 ms 4408 KB Output is correct
5 Correct 209 ms 6604 KB Output is correct
6 Correct 212 ms 7076 KB Output is correct
7 Correct 196 ms 7072 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 3148 KB Output is correct
2 Correct 215 ms 6220 KB Output is correct
3 Correct 257 ms 8640 KB Output is correct
4 Correct 216 ms 7624 KB Output is correct