Submission #553843

#	Time	Username	Problem	Language	Result	Execution time	Memory
553843		Fidan	Addk (eJOI21_addk)	C++17	100 / 100	315 ms	7972 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll inf=(1e18);
const ll N=1'000'010;

ll n, k, i;
vector<ll> v;
vector<ll> sum;
vector<ll> pre;

void update(ll id, ll val, vector<ll> &fen){
	id++;
	while(id<=fen.size()){
		fen[id]+=val;
		id+=id&(-id);
	}
}

ll query(ll id, vector<ll> &fen){
	ll s=0;
	id++;
	while(id>0){
		s+=fen[id];
		id-=id&(-id);
	}
	return s;
}

	
ll prefix(ll l, ll r){
	ll s=0;
	s=query(r, pre)-query(l-1, pre)-(l-1)*(query(r, sum)-query(l-1, sum));
	return s;
}

ll suffix(ll l, ll r){
	ll s=0;
	s=(r-l+2)*(query(r, sum)-query(l-1, sum))-prefix(l, r);
	return s;
}

void solve(ll l, ll r, ll m){
	ll s=0;
	if(2*m>r-l+1) m=r-l-m+2;
	s=prefix(l, l+m-1)+m*(query(r-m, sum)-query(l+m-1, sum))+suffix(r-m+1, r);
	cout<<s<<endl;
}

int main(){
	
	cin>>n>>k;
	v.push_back(0);
	pre.push_back(0);
	sum.push_back(0);
	
	for(i=1; i<=n; i++){
		ll a;
		cin>>a;
		v.push_back(a);
		sum.push_back(0);
		pre.push_back(0);
	}
	for(i=1; i<=n; i++){
		update(i, v[i], sum);
		update(i, v[i]*i, pre);
	}
	ll qu;
	cin>>qu;
	while(qu--){
		ll asdf;
		cin>>asdf;
		
		if(asdf==1){
			vector<ll> c1(k+1);
			vector<ll> c2(k+1);
			for(i=0; i<k; i++){
				cin>>c1[i];
				c2[i]=v[c1[i]];
			}
			c1[k]=c1[0];
			c2[k]=c2[0];
			for(i=0; i<k; i++){
				update(c1[i], c2[i+1]-c2[i], sum);
				update(c1[i], c1[i]*(c2[i+1]-c2[i]), pre);
			}
			for(i=0; i<k; i++){
				v[c1[i]]=c2[i+1];
			}
		}
		
		else {
			ll l, r, m;
			cin>>l>>r>>m;
			solve(l, r, m);
		}
	}
	
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void update(ll, ll, std::vector<long long int>&)':
Main.cpp:15:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  while(id<=fen.size()){
      |        ~~^~~~~~~~~~~~

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