Submission #825627

#	Time	Username	Problem	Language	Result	Execution time	Memory
825627		yusuf12360	Addk (eJOI21_addk)	C++14	100 / 100	226 ms	12688 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
	int line, diag;
	node(int line=0, int diag=0) : line(line), diag(diag) {}
};
node combine(node L, node R) {
	return node(L.line+R.line, L.diag+R.diag);
}
int n, k;
vector<int> a;
vector<node> tr;
void build(int pos=0, int l=0, int r=n-1) {
	if(l==r) {tr[pos]=node(a[l], l*a[r]); return;}
	int mid=l+r>>1;
	build(2*pos+1, l, mid);
	build(2*pos+2, mid+1, r);
	tr[pos]=combine(tr[2*pos+1], tr[2*pos+2]);
}
void update(int idx, int val, int pos=0, int l=0, int r=n-1) {
	if(l==r) {tr[pos]=node(val, idx*val); return;}
	int mid=l+r>>1;
	if(idx<=mid) update(idx, val, 2*pos+1, l, mid);
	else update(idx, val, 2*pos+2, mid+1, r);
	tr[pos]=combine(tr[2*pos+1], tr[2*pos+2]);
}
node get(int ll, int rr, int pos=0, int l=0, int r=n-1) {
	if(ll>rr || ll>r || l>rr) return node();
	if(ll==l && rr==r) return tr[pos];
	int mid=l+r>>1;
	return combine(get(ll, min(rr, mid), 2*pos+1, l, mid), get(max(mid+1, ll), rr, 2*pos+2, mid+1, r));
}
signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	a.resize(n); tr.resize(n << 2);
	for(int &p : a) cin >> p;
	build();
	int q; cin >> q;
	while(q--) {
		int type; cin >> type;
		if(type==1) {
			vector<int> I(k);
			for(int &p : I) cin >> p, --p;
			for(int i=1; i<k; i++) swap(a[I[i-1]], a[I[i]]);
			for(int p : I) update(p, a[p]);
		} else {
			int l, r, m, ans; cin >> l >> r >> m; --l; --r;
			if(r-m+1<=l+m-1) {
				ans=(r-l-m+2)*get(r-m+1, l+m-1).line;
				ans+=get(l, r-m).diag-(l-1)*get(l, r-m).line;
				ans-=get(l+m, r).diag-(r+1)*get(l+m, r).line;
			} else {
				ans=m*get(l+m-1, r-m+1).line;
				ans+=get(l, l+m-2).diag-(l-1)*get(l, l+m-2).line;
				ans-=get(r-m+2, r).diag-(r+1)*get(r-m+2, r).line;
			}
			cout << ans << '\n';
		}
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void build(long long int, long long int, long long int)':
Main.cpp:16:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |  int mid=l+r>>1;
      |          ~^~
Main.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:23:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |  int mid=l+r>>1;
      |          ~^~
Main.cpp: In function 'node get(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:31:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |  int mid=l+r>>1;
      |          ~^~

• Subtask 1: 36 / 36
• Subtask 2: 56 / 56
• Subtask 3: 8 / 8