Submission #1254078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254078		JuanJL	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	2322 ms	96404 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;

#define INF (ll)100000000000000000

struct STree{
	ll n;
	vector<ll> st;
	vector<ll> lazy;
	STree(ll n): n(n), st(4*n+5,-INF), lazy(4*n+5,0) {}
	void push(ll k, ll l, ll r){
		if(lazy[k]==0) return;
		st[k]+=lazy[k];
		if(l+1!=r){
			lazy[2*k]+=lazy[k];
			lazy[2*k+1]+=lazy[k];
		}
		lazy[k]=0;
	}
	void upd(ll k , ll l , ll r, ll  L ,ll R, ll v){
		push(k,l,r);
		if(l>=R||r<=L) return;
		
		if(l>=L&&r<=R){
			lazy[k]+=v;
			push(k,l,r);
			return;
		}
		ll mid = (l+r)/2;
		upd(2*k,l,mid,L,R,v); upd(2*k+1,mid,r,L,R,v);
		st[k]=max(st[2*k],st[2*k+1]);
	}
	
	ll query(ll k, ll l, ll r, ll L, ll R){
		push(k,l,r);
		if(l>=R||r<=L) return -2*INF;
		if(l>=L&&r<=R) return st[k];
		ll mid = (l+r)/2;
		return max(query(2*k,l,mid,L,R),query(2*k+1,mid,r,L,R));
	}
	void upd(ll l ,ll r, ll v){ upd(1,0,n,l,r,v); }
	ll query(ll l ,ll r){ return query(1,0,n,l,r); }
};

vector<pair<ll,ll>> vals; 
ll ind(pair<ll,ll> x){ return lower_bound(ALL(vals),x)-vals.begin(); }

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

	vector<int> nA = A;
	vector<int> res;
	
	
	forn(i,0,SZ(A)) vals.pb({A[i],i});
	forn(i,0,SZ(X)) vals.pb({V[i],X[i]});
	
	sort(ALL(vals));
	vals.erase(unique(ALL(vals)), vals.end());
	
	STree st(SZ(vals));
	//forn(j,0,SZ(vals)) cout<<st.query(j,j+1)<<" "; cout<<'\n';
	
	forn(i,0,SZ(A)){
		ll I = ind({A[i],i});
		st.upd(I,I+1,INF+i);
		st.upd(I+1,SZ(vals),-1);
		//forn(j,0,SZ(vals)) cout<<st.query(j,j+1)<<" "; cout<<'\n';
	}
//	cout<<"------------------\n";
//	
//	forn(j,0,SZ(vals)) cout<<st.query(j,j+1)<<" "; cout<<'\n';
	
	forn(i,0,SZ(X)){
		ll I = ind({A[X[i]],X[i]});
		st.upd(I,I+1,-(INF+X[i]));
		st.upd(I+1,SZ(vals),+1);
		I = ind({V[i],X[i]});
		st.upd(I,I+1,INF+X[i]);
		st.upd(I+1,SZ(vals),-1);
		res.pb(st.query(0,SZ(vals)));
//		forn(j,0,SZ(vals)) cout<<st.query(j,j+1)<<" "; cout<<'\n';
		A[X[i]]=V[i];
	}
	
//	forn(i,0,SZ(A)) is.insert({i,A[i]});
//	
//	iset nis;
//	
//	
//	vector<ll> cnt(SZ(A));
//	ll rres = 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';
//		cnt[i.fst]=ll(SZ(nis)-(nis.order_of_key({i.snd,i.fst})+1));
//	}


//	forn(i,0,SZ(X)){
//		//is.erase(is.find({X[i],nA[X[i]]}));
//		
//		//is.insert({X[i],nA[X[i]]});
//		rres=0;
//		cnt[X[i]]=0;
//		forn(j,0,SZ(A)){
//			if(j>X[i]){
//				if(nA[X[i]]>nA[j]){
//					if(V[i]<=nA[j]) cnt[j]--;
//				}else{
//					if(V[i]>nA[j]) cnt[j]++;
//				}
//			}else{
//				if(j!=X[i] && nA[j]>V[i]) cnt[X[i]]++;
//			}
//			//cout<<cnt[j]<<" ";
//			rres=max(rres,cnt[j]);
//		}
//		
//		nA[X[i]]=V[i];
//		res.pb(rres);
//	}
//	
	
	return res;
}

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