Submission #292944

#	Time	Username	Problem	Language	Result	Execution time	Memory
292944		Hemimor	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	181 ms	17164 KiB

shoes

#include "shoes.h"
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;

class Segment_Tree{
	private:
	int n;
	vi date;
	public:
	Segment_Tree(int n_){
		n=1;
		while(n<n_) n*=2;
		date=vi(2*n-1);
	}
	void Update(int k,int x){
		k+=n-1;
		date[k]+=x;
		while(k>0){
			k=(k-1)/2;
			date[k]=date[k*2+1]+date[k*2+2];
		}
	}
	int Query(int a,int b){
		a+=n-1;b+=n-1;
		int m=0;
		while(a<b){
			if(a%2==0) m+=date[a++];
			if(b%2==0) m+=date[--b];
			a/=2;b/=2;
		}
		return m;
	}
	int Open(int k){return date[k+n-1];}
};

ll count_swaps(vi a){
	ll n=(int)a.size()/2,res=0;
	vvi bl(n+1),br(n+1);
	vp c;
	for(int i=0;i<2*n;i++){
		if(a[i]<0) bl[abs(a[i])].push_back(i);
		else br[abs(a[i])].push_back(i);
	}
	for(int i=1;i<=n;i++){
		int m=bl[i].size();
		for(int j=0;j<m;j++){
			int l=bl[i][j],r=br[i][j];
			if(l>r){
				res++;
				swap(l,r);
			}
			c.push_back({l,r});
		}
	}
	sort(c.begin(),c.end());
	Segment_Tree st(2*n);
	for(auto p:c){
		int l=p.first,r=p.second;
		res+=st.Query(l,r);
		res+=st.Query(r,2*n)*2;
		st.Update(r,1);
	}
	return res;
}

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