oj.uz

Submission #638138

# Submission time Handle Problem Language Result Execution time Memory
638138 2022-09-04T18:20:47 Z Tekor Addk (eJOI21_addk) C++17
100 / 100
 438 ms 12492 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define en '\n'
void boos() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
const int N = 3e5 + 100;
int n,k;
ll t[N * 4],t1[N * 4],t2[N * 4],a[N];
int b[N];
void merg(int v,int tl,int tr) {
	int tm = (tl + tr) / 2;
	t[v] = t[v + v] + t[v + v + 1];
	t1[v] = t1[v + v] + t1[v + v + 1] + (t[v + v + 1] * (ll)(tm - tl + 1));
	t2[v] = t2[v + v] + t2[v + v + 1] + (t[v + v] * (ll)(tr - tm));
}
void build(int v,int tl,int tr) {
	if(tl == tr) {
		t[v] = a[tl];
		t1[v] = a[tl];
		t2[v] = a[tl];
		return;
	}
	int tm = (tl + tr) / 2;
	build(v + v,tl,tm);
	build(v + v + 1,tm + 1,tr);
	merg(v,tl,tr);
}
void upd(int v,int tl,int tr,int pos,ll x) {
	if(tl == tr) {
		t[v] = x;
		t1[v] = x;
		t2[v] = x;
		return;
	}
	int tm = (tl + tr) / 2;
	if(pos <= tm)upd(v + v,tl,tm,pos,x);
	else upd(v + v + 1,tm + 1,tr,pos,x);
	merg(v,tl,tr);
}
ll get(int v,int tl,int tr,int l,int r) {
	if(tl > r || tr < l)return 0;
	if(tl >= l && tr <= r)return t[v];
	int tm = (tl + tr) / 2;
	return get(v + v,tl,tm,l,r) + get(v + v + 1,tm + 1,tr,l,r);
}
ll get1(int v,int tl,int tr,int l,int r) {
	if(tl > r || tr < l)return 0;
	if(tl >= l && tr <= r)return t1[v] + (ll)(tl - l) * t[v];
	int tm = (tl + tr) / 2;
	return get1(v + v,tl,tm,l,r) + get1(v + v + 1,tm + 1,tr,l,r);
}
ll get2(int v,int tl,int tr,int l,int r) {
	if(tl > r || tr < l)return 0;
	if(tl >= l && tr <= r)return t2[v] + (ll)(r - tr) * t[v];
	int tm = (tl + tr) / 2;
	return get2(v + v,tl,tm,l,r) + get2(v + v + 1,tm + 1,tr,l,r);
}
void solve() {
	cin >> n >> k;
	for(int i = 1;i <= n;i++) {
		cin >> a[i];
	}
	build(1,1,n);
	int q;
	cin >> q;
	for(int i = 1;i <= q;i++) {
		int typ;
		cin >> typ;
		if(typ == 1) {
			for(int j = 1;j <= k;j++)cin >> b[j];
			for(int j = 1;j <= k;j++) {
				if(j == k)upd(1,1,n,b[j],a[b[1]]);
				else upd(1,1,n,b[j],a[b[j + 1]]);
			}
			ll last = a[b[1]];
			for(int j = k;j >= 1;j--) {
				ll vv = a[b[j]];
				a[b[j]] = last;
				last = vv;
			}
		}else {
			int l,r,m;
			cin >> l >> r >> m;
			int R = min(l + m - 2,r - m),L = max(r - m + 2,l + m);
			cout << get1(1,1,n,l,R) + get(1,1,n,R + 1,L - 1) * (ll)(R - l + 2ll) + get2(1,1,n,L,r)  << en;
		}
	}
}
int main() {
	solve();
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 9 ms 596 KB Output is correct
5 Correct 12 ms 612 KB Output is correct
6 Correct 16 ms 776 KB Output is correct
7 Correct 17 ms 788 KB Output is correct
8 Correct 20 ms 832 KB Output is correct
9 Correct 33 ms 1328 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 2328 KB Output is correct
2 Correct 91 ms 2500 KB Output is correct
3 Correct 121 ms 4288 KB Output is correct
4 Correct 233 ms 8008 KB Output is correct
5 Correct 327 ms 8800 KB Output is correct
6 Correct 304 ms 8596 KB Output is correct
7 Correct 316 ms 8528 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 4236 KB Output is correct
2 Correct 324 ms 10580 KB Output is correct
3 Correct 438 ms 12492 KB Output is correct
4 Correct 361 ms 11468 KB Output is correct