Submission #1254008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254008		JuanJL	Bubble Sort 2 (JOI18_bubblesort2)	C++20	17 / 100	9090 ms	4316 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i< b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cout.tie(0); cin.tie(0); 
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<pair<ll,ll>,null_type,less<pair<ll,ll>>,rb_tree_tag,tree_order_statistics_node_update> iset;

iset is;

ll solve(vector<int> A){
	
	
	iset nis;
	
	
	ll res = 0;
	
	for(auto i:is){
		nis.insert({i.snd,i.fst});
		//cout<<i.snd<<" "<<ll(SZ(nis)-(nis.order_of_key({i.snd,i.fst})+1))<<'\n';
		
		res+=max((ll)0, ll(SZ(nis)-(nis.order_of_key({i.snd,i.fst})+1)) - res);
	}
	return res;
}


std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){


	forn(i,0,SZ(A)) is.insert({i,A[i]});

	vector<int> nA = A;
	vector<int> res;
	forn(i,0,SZ(X)){
		is.erase(is.find({X[i],nA[X[i]]}));
		nA[X[i]]=V[i];
		is.insert({X[i],nA[X[i]]});
		res.pb(solve(nA));
	}
	
	
	
	
	
	return res;
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40