Submission #1318476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318476		batigol	Bubble Sort Machine (JOI25_bubble)	C++20	0 / 100	456 ms	11440 KiB

bubble

/*
 */

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

#define ll long long
#define vll vector<ll>
#define pll pair<ll,ll>
#define iter vector<ll>::iterator
#define fir first
#define sec second
#define pushf push_front
#define pushb push_back
#define popf pop_front
#define popb pop_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define f(a) for(ll _ = 0; _ < a; _++)
#define fa(i,a) for(ll i = 0; i < a; i++)
#define fab(i,a,b) for(ll i = a; i < b; i++)
#define rf(a) for (ll _ = (a)-1; _ >= 0; --_)
#define rfa(i,a) for (ll i = (a)-1; i >= 0; --i)
#define rfab(i,a,b) for (ll i = (b)-1; i >= a; --i)
#define inf LLONG_MAX/2
#define ninf LLONG_MIN/2
#define input(a,b) a b; cin >> b

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	ll n; cin>>n;
	vll arr(n);
	fa(i,n) cin>>arr[i];
	vll num;
	fa(i,n) if(arr[i]==1) num.pushb(i);
	vll pref(n,0);
	fa(i,n){
		if(i!=0) pref[i] = pref[i-1];
		pref[i] += (arr[i]==2);
	}
	ll q; cin>>q;
	ll k = 0;
	f(q){
		ll x;
		cin>>x;
		if(x==1) k++;
		else{
			ll l, r; cin>>l>>r;
			l--; r--;
			ll lo = 0, hi = num.size()-1;
			ll res1 = 0;
			while(lo<=hi){
				ll mid = (lo+hi)/2;
				if(num[mid]- min(pref[num[mid]],k)>=l){
					res1 = mid;
					hi = mid - 1;
				}else{
					lo = mid + 1;
				}
			}
			lo = 0, hi = num.size()-1;
			ll res2 = num.size();
			while(lo<=hi){
				ll mid = (lo+hi)/2;
				if(num[mid] - min(pref[num[mid]],k)>r){
					res2 = mid;
					hi = mid - 1;
				}else{
					lo = mid + 1;
				}
			}
			//cout<<res1<<"-"<<res2<<endl;
			ll temp = max(0ll, res2 - res1);
			cout<<temp + (r-l-temp+1)*2<<endl;
		}
	}
    return 0;
}

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