Submission #638136

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
638136	2022-09-04T18:16:37 Z	Tekor	Addk (eJOI21_addk)	C++17	92 / 100	356 ms	11176 KB

Main

#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;
		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++)upd(1,1,n,b[j],a[b[j == k ? 1 : j + 1]]);
		}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	13 ms	672 KB	Output is correct
6	Correct	16 ms	924 KB	Output is correct
7	Correct	25 ms	952 KB	Output is correct
8	Correct	23 ms	980 KB	Output is correct
9	Correct	30 ms	1452 KB	Output is correct

Subtask #2

56.0 / 56.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	2720 KB	Output is correct
2	Correct	97 ms	3144 KB	Output is correct
3	Correct	137 ms	5244 KB	Output is correct
4	Correct	241 ms	9724 KB	Output is correct
5	Correct	354 ms	11176 KB	Output is correct
6	Correct	356 ms	11120 KB	Output is correct
7	Correct	322 ms	11060 KB	Output is correct

Subtask #3

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	202 ms	5964 KB	Output isn't correct
2	Halted	0 ms	0 KB	-