제출 #1321706

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1321706		batigol	Bubble Sort Machine (JOI25_bubble)	C++20	83 / 100	2098 ms	129328 KiB

bubble

/*
 */
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#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;
using namespace __gnu_pbds;


template<typename T>
using ordered_set = tree<
    T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


struct node{
	ll s, e, val;
	node *left, *right;
	node(ll s, ll e):s(s), e(e) {
		val = 0;
		if(s==e) return;
		ll mid = (s+e)/2;
		left = new node(s, mid);
		right = new node(mid+1, e);
	}
	void update(ll k, ll v){
		if(s==e){
			val = v;
			return;
		}
		ll mid = (s+e)/2;
		if(k<=mid) left->update(k,v);
		else right->update(k,v);
		val = left->val + right->val; 
	}
	ll query(ll l, ll r){
		if(l>e||r<s) return 0;
		if(l<=s&&e<=r) return val;
		return left->query(l,r) + right->query(l,r);
	}
} *st;
struct skib{
	ll i, k, n;
	bool operator<(const skib &other) const{
		return (k+n) < (other.k + other.n);
	}
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	ll n; cin>>n;
	st = new node(0, n-1);
	vector <pll> temp(n);
	fa(i,n){
		ll a; cin>>a;
		temp[i] = {a, i};
	}
	sort(all(temp),[&](pll a,pll b){
		return a.fir<b.fir;
	});
	vector <pll> arr(n);
	fa(i,n){
		arr[temp[i].sec] = {temp[i].fir, i}; 
	}
	ll q; cin>>q;
	ll k = 0;
	vector <skib> query;
	ll counter = 0;
	fa(i,q){
		ll t; cin>>t;
		if(t==1) k++;
		else{
			ll l, r; cin>>l>>r;
			--l; --r;
			query.pushb({counter, k, l-1});
			query.pushb({counter, k, r});
			counter++;
		}
	}
	ordered_set <pll> s;
	sort(all(query));
	ll j = 0;
	vll res((ll)query.size()/2, -1);
	for(auto i:query){
		while(j<n && j<=i.n+i.k){
			st->update(arr[j].sec, arr[j].fir);
			s.insert({arr[j].fir, arr[j].sec});
			j++;
		}
		if(i.n!=-1){
			auto val = s.find_by_order(i.n);
			ll cali = st->query(0,val->sec);
			if(res[i.i]==-1) res[i.i] = (cali);
			else res[i.i] = abs(res[i.i]-cali);
		}else{
			if(res[i.i]==-1) res[i.i] = (0);	
		}
	}
	fa(i, (ll) query.size()/2){
		cout<<res[i]<<endl;
	}
    return 0;
}

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