Submission #162802

#	Time	Username	Problem	Language	Result	Execution time	Memory
162802		kikkatugno	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	2 ms	376 KiB

shoes

#include<iostream>
#include<set>
#include<vector>
using namespace::std;
 
set<pair<int,int>> s;
int st[800005];
 
int query(int i,int l,int r,int s,int e){
	if(s<=l && r<=e)
		return st[i];
	if(s>=r || e<=l)
		return 0;
	int mid=l+(r-l)/2;
	return query(i*2,l,mid,s,e)+query(i*2+1,mid,r,s,e);
}
 
void point_upd(int i,int l,int r,int ind){
	if(l+1==r && l==ind){
		st[i]++;
		return;
	}
	if(ind>=r || ind<l)
		return ;
	int mid=l+(r-l)/2;
	st[i]++;
	if(ind>=mid)
		point_upd(i*2+1,mid,r,ind);
	else point_upd(i*2,l,mid,ind);
}
 
int count_swaps(vector<int,allocator<int>> ar){
	int n=ar.size();
	//cin>>n;
	long long int ans=0;
	for(int i=0;i<2*n;i++)
		/*cin>>ar[i],*/s.insert({ar[i],i});
	//build(1,0,2*n);
	for(int i=0;i<2*n;i++)
		if(s.find({ar[i],i})!=s.end()){
			pair<int,int> t=*(s.lower_bound({-ar[i],0}));
			ans+=t.second-i-(ar[i]<0)-query(1,0,2*n,i,t.second);
			cout<<t.second<<' '<<i<<' '<<ar[i]<<' '<<query(1,0,2*n,i,t.second)<<'\n';
			point_upd(1,0,2*n,t.second);
			s.erase({ar[i],i});
			s.erase(t);
		}
	return ans;
}

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