oj.uz

Submission #638137

# Submission time Handle Problem Language Result Execution time Memory
638137 2022-09-04T18:18:37 Z Tekor Addk (eJOI21_addk) C++17
92 / 100
 391 ms 8716 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]]);
			}
		}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 468 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 8 ms 468 KB Output is correct
5 Correct 12 ms 596 KB Output is correct
6 Correct 15 ms 792 KB Output is correct
7 Correct 20 ms 788 KB Output is correct
8 Correct 21 ms 828 KB Output is correct
9 Correct 30 ms 1276 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 2232 KB Output is correct
2 Correct 106 ms 2584 KB Output is correct
3 Correct 128 ms 4296 KB Output is correct
4 Correct 235 ms 8060 KB Output is correct
5 Correct 391 ms 8716 KB Output is correct
6 Correct 302 ms 8572 KB Output is correct
7 Correct 368 ms 8600 KB Output is correct

Subtask #3
0 / 8.0

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