oj.uz

Submission #477696

# Submission time Handle Problem Language Result Execution time Memory
477696 2021-10-03T06:30:17 Z luka1234 Addk (eJOI21_addk) C++14
100 / 100
 497 ms 10564 KB 
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
ll n,q,q1;
ll t1[400001];
ll t2[400001];
ll a[100001];
void build(ll v,ll tl,ll tr){
	if(tl==tr){
		t1[v]=a[tl];
		t2[v]=a[tl]*tl;
	}
	else{
		ll m=(tl+tr)/2;
		build(2*v,tl,m);
		build(2*v+1,m+1,tr);
		t1[v]=t1[2*v]+t1[2*v+1];
		t2[v]=t2[2*v]+t2[2*v+1];
	}
}
pair<ll,ll> get(ll v,ll tl,ll tr,ll l,ll r){
	if(tl==l&&tr==r){
		return {t1[v],t2[v]};
	}
	ll m=(tl+tr)/2;
	if(r<=m){
		return get(2*v,tl,m,l,r);
	}
	else{
		if(l>m){
			return get(2*v+1,m+1,tr,l,r);
		}
		else{
			pair<ll,ll> pir=get(2*v,tl,m,l,m);
			pair<ll,ll> meo=get(2*v+1,m+1,tr,m+1,r);
			pair<ll,ll> mes;
			mes.ff=pir.ff+meo.ff;
			mes.ss=pir.ss+meo.ss;
			return mes;
		}
	}
}
void update(ll v,ll tl,ll tr,ll x,ll p){
	if(tl==tr){
		t1[v]=x;
		t2[v]=p*x;
	}
	else{
		ll m=(tl+tr)/2;
		if(p<=m)
		   update(2*v,tl,m,x,p);
		else
		   update(2*v+1,m+1,tr,x,p);
		t1[v]=t1[2*v]+t1[2*v+1];
		t2[v]=t2[2*v]+t2[2*v+1];
	}
}
int main(){
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>q;
	for(ll k=1;k<=n;k++)
	    cin>>a[k];
	build(1,1,n);
	cin>>q1;
	while(q1--){
		ll x;
		cin>>x;
		if(x==2){ 
			ll l,r,m;
			cin>>l>>r>>m;
			if(m==1||m==(r-l+1)){
				ll ans=get(1,1,n,l,r).ff;
				cout<<ans<<"\n";
				continue;
			}
			ll v=(r-l+1)/2+1;
			ll m1;
			if(m<=v){
				m1=m-1;
				if(((r-l+1)%2==0)&&(m==v))
				   m1--;
			}
			else{
				m1=(r-l+1)-m;
			}
			ll pir=0,meo=0,mes=0;  
			pair<ll,ll> vv=get(1,1,n,l,l+m1-1);
			ll f=l-1;
			pir=vv.ss-vv.ff*f;
  			vv=get(1,1,n,r-m1+1,r);
			f=r+1;
			meo=vv.ff*f-vv.ss;
			vv=get(1,1,n,l+m1,r-m1);
			ll fff=m1+1;
			mes=vv.ff*fff;
			cout<<pir+meo+mes<<"\n";
		}
		else{
			ll b[q+1];
			for(ll k=1;k<=q;k++)
			    cin>>b[k];
			ll f=a[b[1]];
			for(ll k=1;k<q;k++){
				a[b[k]]=a[b[k+1]];
				update(1,1,n,a[b[k+1]],b[k]);
			}
			a[b[q]]=f;
			update(1,1,n,f,b[q]);
		}
	}
    return 0;
}

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 332 KB Output is correct
3 Correct 7 ms 332 KB Output is correct
4 Correct 10 ms 500 KB Output is correct
5 Correct 13 ms 460 KB Output is correct
6 Correct 17 ms 716 KB Output is correct
7 Correct 23 ms 652 KB Output is correct
8 Correct 22 ms 696 KB Output is correct
9 Correct 35 ms 972 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 1680 KB Output is correct
2 Correct 127 ms 1960 KB Output is correct
3 Correct 146 ms 3172 KB Output is correct
4 Correct 259 ms 7664 KB Output is correct
5 Correct 423 ms 9092 KB Output is correct
6 Correct 368 ms 8944 KB Output is correct
7 Correct 381 ms 8816 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 3180 KB Output is correct
2 Correct 326 ms 8524 KB Output is correct
3 Correct 497 ms 10564 KB Output is correct
4 Correct 398 ms 9416 KB Output is correct