oj.uz

Submission #553843

# Submission time Handle Problem Language Result Execution time Memory
553843 2022-04-27T07:28:08 Z Fidan Addk (eJOI21_addk) C++17
100 / 100
 315 ms 7972 KB 
#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

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.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 316 KB Output is correct
3 Correct 6 ms 404 KB Output is correct
4 Correct 9 ms 520 KB Output is correct
5 Correct 10 ms 568 KB Output is correct
6 Correct 14 ms 596 KB Output is correct
7 Correct 16 ms 720 KB Output is correct
8 Correct 19 ms 712 KB Output is correct
9 Correct 26 ms 1080 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1660 KB Output is correct
2 Correct 81 ms 2188 KB Output is correct
3 Correct 103 ms 2812 KB Output is correct
4 Correct 182 ms 4752 KB Output is correct
5 Correct 258 ms 6796 KB Output is correct
6 Correct 247 ms 6452 KB Output is correct
7 Correct 247 ms 6576 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 3896 KB Output is correct
2 Correct 243 ms 5772 KB Output is correct
3 Correct 315 ms 7972 KB Output is correct
4 Correct 283 ms 6976 KB Output is correct