Submission #827908

#	Time	Username	Problem	Language	Result	Execution time	Memory
827908		ZeroCool	Addk (eJOI21_addk)	C++14	100 / 100	1666 ms	7876 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define mp make_pair
#define pb push_back

using ll = long long;
using ld = long double;


void solve(int T);
void pre();

const int mxn = 1e5 + 5;
const int SQRT = 500;
const int LOG = 20;
const int inf = 1e18;
const int mod = 1e9 + 7;
const ld eps = 1e-9;

int32_t main(){
	pre();
	int tt = 1;
	//cin>>tt;
	for(int i = 1;i<=tt;i++)solve(i);
    return 0;
}


struct FenwickTree{
	vector<int> bit;
	vector<int> val;
	int n;
	FenwickTree(int _n){
		n = _n + 17;
		bit.resize(n);
		val.resize(n);
	}

	

	void upd(int i,int v){
		val[i] += v;
		for(i++;i<n;i += i & -i)bit[i] += v;
	}

	int que(int pos){
		int ans = 0;
		for(pos++;pos;pos -= pos & -pos)ans += bit[pos];
		return ans;
	}

	void update(int ind,int v){
		upd(ind, -val[ind]);
		upd(ind, v);
	}

	int query(int a,int b){
		return que(b) - que(a-1);
	}
};

void pre(){
	#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
	#endif
	
}

void solve(int T){
	int n,k;
	cin>>n>>k;
	int A[n];
	FenwickTree fwt(n);
	for(int i = 0;i<n;i++){
		cin>>A[i];
		fwt.update(i, A[i]);
	}

	int q;
	cin>>q;
	while(q--){
		int op;
		cin>>op;
		if(op == 1){
			int ind[k];
			for(int i = 0;i<k;i++){
				int a;
				cin>>a;
				a--;
				ind[i] = a;
			}

			int cur = A[ind[0]];
			for(int i = 1;i<k;i++){
				A[ind[i-1]] = A[ind[i]];
			}
			A[ind[k-1]] = cur;
			for(int i = 0;i<k;i++){
				fwt.update(ind[i], A[ind[i]]);
			}
		}else{
			int l,r,m;
			cin>>l>>r>>m;

			l--;
			r--;
			int ans = fwt.query(l,r);
			int p1 = l;
			int p2 = r;
			int s = 0;
			int c = 0;

			while(p1 <= p2 && p2 >= l + m - 1 && c < m){
				s += ans;
				ans -= (A[p1] + A[p2]);
				p2--;
				p1++;
				c++;
			}
			cout<<s<<endl;
		}
	}
}

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