oj.uz

Submission #827908

# Submission time Handle Problem Language Result Execution time Memory
827908 2023-08-16T22:24:54 Z ZeroCool Addk (eJOI21_addk) C++14
100 / 100
 1666 ms 7876 KB 
#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.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 8 ms 472 KB Output is correct
5 Correct 11 ms 468 KB Output is correct
6 Correct 14 ms 548 KB Output is correct
7 Correct 18 ms 596 KB Output is correct
8 Correct 22 ms 664 KB Output is correct
9 Correct 36 ms 828 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 1476 KB Output is correct
2 Correct 212 ms 2112 KB Output is correct
3 Correct 348 ms 2672 KB Output is correct
4 Correct 1133 ms 4608 KB Output is correct
5 Correct 1666 ms 6600 KB Output is correct
6 Correct 1450 ms 6316 KB Output is correct
7 Correct 1285 ms 6348 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 3796 KB Output is correct
2 Correct 1072 ms 5628 KB Output is correct
3 Correct 282 ms 7876 KB Output is correct
4 Correct 1608 ms 6868 KB Output is correct