oj.uz

Submission #475447

# Submission time Handle Problem Language Result Execution time Memory
475447 2021-09-22T13:51:04 Z keta_tsimakuridze Addk (eJOI21_addk) C++14
100 / 100
 684 ms 9412 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, n, q, a[N], tree[4 * N],lazy[4*N],b[20];
void push(int u,int l,int r) {
	tree[u] += lazy[u] * (r - l + 1);
	if(l != r) {
		lazy[2 * u] += lazy[u];
		lazy[2 * u + 1] += lazy[u];
	}
	lazy[u] = 0;
}
void upd(int u,int start,int end,int l,int r,int val) {
	push(u,l,r);
	if(l > end || r < start) return;
	if(start <= l && r <= end) {
		lazy[u] = val;
		push(u,l,r);
		return;
	}
	int mid = (l + r)/2;
	upd(2 * u, start, end, l, mid, val);
	upd(2 * u + 1, start, end, mid + 1, r, val);
	tree[u] = tree[2 * u] + tree[2 * u + 1];
}
int get(int u,int start,int end,int l,int r) {
	push(u,l,r);
	if(l > end || r < start) return 0;
	if(start <= l && r <= end) return tree[u];
	int mid = (l + r)/2;
	return get(2 * u, start,end,l,mid) + get(2 * u + 1,start,end,mid+1,r);
}
main(){
	int K;
	cin >> n >> K;
//	if(K > 1) return 0;
	for(int i = 1; i <= n; i++) cin >> a[i], upd(1,i,n,1,n,a[i]);
	
	int q;
	cin >> q;
	while(q--) {
		int t;
		cin >> t;
		if(t == 1) {
			for(int i = 1; i <= K; i++) {
				cin >> b[i];
			}
				b[K + 1] = b[1];
			for(int i = 1; i <= K; i++)
				upd(1,b[i],n,1,n,a[b[i + 1]] - a[b[i]]);
			///a[b[1]] = a[b[2]].....
			int saved = a[b[1]];
			for(int i = 1; i <= K; i++) {
				a[b[i]] = a[b[i + 1]];
			}
			a[b[K]] = saved;
		//	for(int i = 1; i <= K; i++) cout << a[b[i]] << endl;
			continue;
		}
		int l,r,m;
		cin >> l >> r >> m;
	//	cout << get(1,l + m - 1,r,1,n) <<" "<<l + m - 1 <<"__"<<r<<endl;
		cout << get(1,l + m - 1, r, 1, n) - get(1,l - 1, r - m, 1,n) << endl;
	}
 }

Compilation message

Main.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 | main(){
      | ^~~~

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 356 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 12 ms 460 KB Output is correct
5 Correct 16 ms 460 KB Output is correct
6 Correct 20 ms 644 KB Output is correct
7 Correct 24 ms 688 KB Output is correct
8 Correct 29 ms 772 KB Output is correct
9 Correct 40 ms 964 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 1724 KB Output is correct
2 Correct 134 ms 1956 KB Output is correct
3 Correct 186 ms 3364 KB Output is correct
4 Correct 322 ms 5940 KB Output is correct
5 Correct 499 ms 6624 KB Output is correct
6 Correct 438 ms 6488 KB Output is correct
7 Correct 448 ms 6464 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 3140 KB Output is correct
2 Correct 427 ms 8592 KB Output is correct
3 Correct 684 ms 8772 KB Output is correct
4 Correct 498 ms 9412 KB Output is correct