oj.uz

Submission #580839

# Submission time Handle Problem Language Result Execution time Memory
580839 2022-06-22T01:15:03 Z penguin133 Addk (eJOI21_addk) C++14
100 / 100
 429 ms 22164 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pi pair<int, int> 
#define pii pair<int, pair<int, int> >
int P[200005], P2[200005], A[200005], S[200005];
int n,k;
struct node{
	int s,e,m,val,val2,val3;
	node *l, *r;
	node(int _s, int _e){
		val = val2 = val3 = 0;
		s = _s, e = _e, m = (s + e)/2;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void update(int p, int v){
		if(s == e)val = v, val2 = s*v, val3 = (n-s+1)*v;
		else{
			if(p <= m)l->update(p,v);
			else r->update(p,v);
			val = l->val + r->val;
			val2 = l->val2 + r->val2;
			val3 = l->val3 + r->val3;
		}
	}
	int query(int a, int b){
		if(s == a && e == b)return val;
		else if(b <= m)return l->query(a,b);
		else if(a > m)return r->query(a,b);
		else return l->query(a,m) + r->query(m+1,b);
	}
	int query2(int a, int b){
		if(s == a && e == b)return val2;
		else if(b <= m)return l->query2(a,b);
		else if(a > m)return r->query2(a,b);
		else return l->query2(a,m) + r->query2(m+1,b);
	}
	int query3(int a, int b){
		if(s == a && e == b)return val3;
		else if(b <= m)return l->query3(a,b);
		else if(a > m)return r->query3(a,b);
		else return l->query3(a,m) + r->query3(m+1,b);
	}
}*root;
 
void solve(){
	cin >> n >> k;
	root = new node(1, n);
	for(int i=1;i<=n;i++){
		cin >> A[i];
		root->update(i, A[i]);
	}
	int q;cin >> q;
	while(q--){
		int x;cin >> x;
		if(x == 1){
			int p;cin >> p;int prev = p;p = A[p];
			for(int i=2;i<=k;i++){
				int x;cin >> x;
				A[prev] = A[x];
				root->update(prev, A[x]);
				prev = x;
			}
			root->update(prev, p);
			A[prev] = p;
		}
		else{
			int l,r,m;
			cin >> l >> r >> m;
			int tmp = (r-l+1);
			m = min(m, tmp+1-m);
			int ans = 0;
			if(m > 1)ans += root->query2(l, l+m-2) - (l-1)*(root->query(l, l+m-2));
			if(m > 1)ans += root->query3(r-m+2, r) - (n-r)*(root->query(r-m+2, r));
			if(r-m+1 >= l+m-1)ans += m*(root->query(l+m-1, r-m+1));
			cout << ans << '\n';
		}
	}
}
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message

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

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 4 ms 596 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 8 ms 980 KB Output is correct
6 Correct 9 ms 1216 KB Output is correct
7 Correct 11 ms 1396 KB Output is correct
8 Correct 13 ms 1492 KB Output is correct
9 Correct 21 ms 2004 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3788 KB Output is correct
2 Correct 63 ms 5604 KB Output is correct
3 Correct 98 ms 7376 KB Output is correct
4 Correct 179 ms 12868 KB Output is correct
5 Correct 264 ms 18232 KB Output is correct
6 Correct 242 ms 18128 KB Output is correct
7 Correct 287 ms 18048 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 9000 KB Output is correct
2 Correct 253 ms 16992 KB Output is correct
3 Correct 429 ms 22164 KB Output is correct
4 Correct 283 ms 20976 KB Output is correct