Submission #1308642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308642		vtnoo	Bubble Sort Machine (JOI25_bubble)	C++20	100 / 100	1183 ms	85820 KiB

bubble

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define me(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
const int MAXN=5e5+5;
ll A[MAXN],sum[MAXN*4],tam[MAXN*4];
vector<ii>ini[MAXN],fin[MAXN];
int n;
void upd(int p,int x,int v=1,int s=0,int e=n-1){
	if(s==e){
		sum[v]+=x;
		tam[v]++; 
		return; 
	}
	int m=(s+e)/2;
	if(p<=m)upd(p,x,v*2,s,m);
	else upd(p,x,v*2+1,m+1,e);
	sum[v]=sum[v*2]+sum[v*2+1];
	tam[v]=tam[v*2]+tam[v*2+1];
}
ll kth_sum(ll k,int v=1,int s=0,int e=n-1){
	if(tam[v]==0)return 0;
	if(s==e){
		ll x=sum[v]/tam[v];
		return x*k*1ll;
	}
	int m=(s+e)/2;
	if(k<=tam[v*2])return kth_sum(k,v*2,s,m);
	else return sum[v*2]+kth_sum(k-tam[v*2],v*2+1,m+1,e);
}
int main(){FIN;
	cin>>n;
	vi compress;
	fore(i,0,n){
		cin>>A[i];
		compress.pb(A[i]);
	}
	sort(ALL(compress));
	compress.erase(unique(ALL(compress)),compress.end());
	fore(i,0,n){
		A[i]=lower_bound(ALL(compress),A[i])-compress.begin();
	}
	int Q;cin>>Q;
	int lim=0,C=0;
	while(Q--){
		int t;cin>>t;
		if(t==1)lim++;
		else{
			int l,r;cin>>l>>r;
			l--;r--;
			ini[min(n-1,l+lim-1)].pb({l,C});
			fin[min(n-1,r+lim)].pb({r+1,C});
			C++;
		}
	}
	vi ans(C,0);
	//~ cout<<"HOLA"<<endl;
	fore(i,0,n){
		upd((int)A[i],(int)compress[A[i]]);
		for(auto[j,idx]:ini[i]){
			ans[idx]-=kth_sum(j);
			//~ cout<<"RESTA :"<<idx<<" "<<ans[idx]<<endl;
		}
		for(auto[j,idx]:fin[i]){
			ans[idx]+=kth_sum(j);
			//~ cout<<"SUMA :"<<idx<<" "<<ans[idx]<<endl;
		}
	}
	//~ cout<<"HOLAA"<<endl;
	fore(i,0,C)cout<<ans[i]<<endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 29 / 29
• Subtask 6: 17 / 17