Submission #1022667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022667		sopaconk	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	491 ms	166224 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
using lli=long long int;
#define pb push_back
#define deb(x) cout<<#x<<": "<<x<<endl;

struct segtree{
	lli l,r;
	lli sum;
	segtree *left, *right;
	segtree(lli a, lli b): l(a), r(b){
		if(l==r){
			sum=1;
		}
		else{
			lli m=(l+r)/2;
			left=new segtree(l,m);
			right=new segtree(m+1,r);
			sum=left->sum+right->sum;
		}
	}
	void update(lli p, lli val){
		if(l==r){
			sum=val;
			return;
		}
		lli m=(l+r)/2;
		if(p<=m) left->update(p, val);
		else right->update(p,val);
		sum=left->sum+right->sum;
	}
	lli query(lli a, lli b){
		if(a<=l && r<=b) return sum;
		if(b<l || r<a) return 0;
		return left->query(a,b)+right->query(a,b);
	}

};

long long count_swaps(vector<int> s) {
	map<lli, queue<lli>> mp;
	lli n=s.size();
	for(lli i=0; i<n; ++i){
		mp[s[i]].push(i);
	}
	segtree tree(0,n-1);
	lli ans=0;
	vector<bool> visited(n, false);
	for(lli i=0; i<n; ++i){
		if(visited[i]) continue;
		mp[s[i]].pop();
		lli x=mp[-s[i]].front();
		mp[-s[i]].pop();
	
		ans+=tree.query(i+1, x-1);
		if(s[i]>0) ans++;
		tree.update(i,0);
		tree.update(x,0);
		visited[x]=true;
	}
	return ans;

}

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