Submission #58413

#	Time	Username	Problem	Language	Result	Execution time	Memory
58413		khohko	Bubble Sort 2 (JOI18_bubblesort2)	C++17	17 / 100	9070 ms	1844 KiB

bubblesort2

#include<bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;

#define ll int
#define fr first
#define sc second
#define pb push_back
#define ARRS ((ll)(2e6+100))
#define MAX ((ll)(1e17+100))

ll fw[ARRS];
ll add(ll i,ll x){
	i++;
	while(i<=8005){
		fw[i]+=x;
		i+=i&-i;
	}
}

ll sum(ll i){
	i++;
	ll p=0;
	while(i>0){
		p+=fw[i];
		i-=i&-i;
	}
	return p;
}


ll t[8005];
ll slv(vector<ll> a){
	for(int i=0; i<8005; i++)fw[i]=0;
	ll n=a.size();
	vector<pair<ll,ll> > b;
	for(int i=0; i<n; i++)b.pb({a[i],i});
	sort(b.begin(),b.end());
	ll c=1;
//	for(int i=0; i<n; i++)cout<<a[i]<<" \n"[i==n-1];
	for(int i=0; i<n; i++){
		if(i&&b[i].fr!=b[i-1].fr)c++;
		a[b[i].sc]=c;
	}
//	for(int i=0; i<n; i++)cout<<a[i]<<" \n"[i==n-1];


	for(int i=n-1; i>=0; i--){
		t[i]=sum(a[i]-1);
		add(a[i],1);
	}
	ll pas=0;
	for(int i=0; i<8005; i++)fw[i]=0;
//	for(int i=0; i<n; i++)
//		cout<<a[i]<<" \n"[i==n-1];
	for(int i=0; i<n; i++){
		//cout<<t[i]<<" "<<sum(n-a[i]-1)<<endl;
		pas=max(pas,sum(n-a[i]-1)+(t[i]?1:0));
		add(n-a[i],1);
	}
	return pas;
}

vector<int> countScans(vector<int> a,vector<int> X,vector<int> V){
	ll n;
	n=a.size();
	ll q=X.size();
	vector<ll> PAS;
//	for(int i=0; i<q; i++){
//		ll k=X[i];
//		ll p=V[i];
//		s[a[k]].erase(k);
//		a[k]=p;
//		s[a[k]].insert(k);
//		ll pas=0;
//		for(int j=1; j<=100; j++){
//			if(st[j].size())
//				v.pb({*st[j].begin(),j});
//			if(st[j].size()>1)
//				v.pb({*(--st[j].end()),j});
//			pas+=max(0,st[j].size()-2);
//		}
//		sort(v.begin(),v.end());
//		for(auto x:v){
//			g.pb(x.sc);
//		}
//		PAS.pb(pas+slv(g));
//	}
	for(int i=0; i<q; i++){
		ll k=X[i];
		ll p=V[i];
		a[k]=p;
//		cout<<slv(a)<<endl;
		PAS.pb(slv(a));
	}
//	cout<<c<<endl;
//	cout<<"-----"<<endl;
	return PAS;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'int add(int, int)':
bubblesort2.cpp:19:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:65:5: warning: variable 'n' set but not used [-Wunused-but-set-variable]
  ll n;
     ^

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