Submission #1308338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308338		vtnoo	Bubble Sort Machine (JOI25_bubble)	C++20	15 / 100	455 ms	7532 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<int> vi;
const int MAXN=5e5+5;
ll A[MAXN];
int main(){FIN;
	int n;cin>>n;
	vi o;
	fore(i,0,n){
		cin>>A[i];
		if(A[i]==1)o.pb(i);
	}
	sort(ALL(o));
	int Q;cin>>Q;
	int c=0;
	auto ones=[&](int i)->int{
		int j=upper_bound(ALL(o),i+c)-o.begin();
		return min(i+1,j);
	};
	auto get=[&](int l,int r)->int{
		int sum=(r-l+1)*2;
		//~ cout<<sum<<" "<<ones(r)<<" "<<ones(l-1)<<endl;
		return sum-(ones(r)-ones(l-1));
	};
	while(Q--){
		int t;cin>>t;
		if(t==1){
			c++;
		}else{
			int a,b;cin>>a>>b;a--;b--;
			cout<<get(a,b)<<endl;
		}
	}
}

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