Submission #211185

#	Time	Username	Problem	Language	Result	Execution time	Memory
211185		thomaswang	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	305 ms	275812 KiB

shoes

#include <bits/stdc++.h>
#define ericxiao cin.tie(0); ios_base::sync_with_stdio(false);
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int,int> pii;
const int maxn=2e5+10;
deque<int> posl[maxn],posr[maxn];
struct BIT{
	int v[maxn],n;
	int lb(int x){return x&(-x);}
	void init(int x){n=x; for(int i=1;i<=n;i++) v[i]=lb(i);}
	void modify(int x,int k){while(x<=n) v[x]+=k,x+=lb(x);}
	int query(int x){int t=0; while(x>0) t+=v[x],x-=lb(x); return t;}
	int get(int l,int r){return query(r+1)-query(l);}
	void del(int x){modify(x+1,-1);}
	void print(){for(int i=0;i<n;i++) cout<<get(i,i)<<' '; cout<<endl;}
} tree;
int count_swaps(vector<signed> v){
	int n=v.size(),ans=0; tree.init(n);
	for(int i=0;i<n;i++){
		if(v[i]>0) posr[v[i]].push_back(i);
		else posl[-v[i]].push_back(i);
	}
	// for(int i=1;i<=n;i++){
	// 	cout<<i<<": "<<endl;
	// 	for(auto &j:posl[i]) cout<<j<<' '; cout<<endl;
	// 	for(auto &j:posr[i]) cout<<j<<' '; cout<<endl;
	// }
	// tree.print();
	for(int i=0;i<n;i++){
		int p=v[i];
		if(p==0) continue;
		if(p>0)
			ans+=tree.get(i,posl[p].front())-1;
		else
			ans+=tree.get(i+1,posr[-p].front())-1;
		tree.del(posl[abs(p)].front()); tree.del(posr[abs(p)].front());
		v[posl[abs(p)].front()]=0; v[posr[abs(p)].front()]=0;
		posl[abs(p)].pop_front(); posr[abs(p)].pop_front();
		// tree.print();
		// for(int j=0;j<n;j++) cout<<v[j]<<' '; cout<<endl;
		// cout<<"ans: "<<ans<<endl;
	}
	return ans;
}
// signed main(){
// 	int n; cin>>n;
// 	vector<int> v(n);
// 	for(int i=0;i<n;i++) cin>>v[i];
// 	cout<<count_swaps(v)<<endl;
// 	return 0;
// }

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15