Submission #615911

#	Time	Username	Problem	Language	Result	Execution time	Memory
615911		angelo_torres	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	92 ms	73668 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define ff first
#define ss second

using namespace std;

typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> ii;

const int N = 1e5 + 10;

int n,a[N<<1],cn = 0;
vi s;
deque<ii> d[N];

struct Fenwick_Tree{
	int n,p[N<<1];
	void up(int ps,int dl){
		for(; ps <= n; ps = (ps|(ps-1))+1)
			p[ps] += dl;
	}
	int get(int ps){
		int ans = 0;
		for(; ps >= 1; ps = (ps&(ps-1)))
			ans += p[ps];
		return ans;
	}
	int ran(int l,int r){
		if(l > r) return 0;
		return get(r)-get(l-1);
	}
} st;

ll count_swaps(vi S){
	s = S;
	n = ((int) s.size())>>1;
	for(int i = 0; i < (n<<1); ++i){
		int id = abs(s[i]), sg = (s[i] < 0 ? 0 : 1);
		if(d[id].empty() or d[id].back().ss == sg){
			d[id].push_back({i,sg});
			if(sg == 0) 
				a[i] = cn<<1;
			else
				a[i] = (cn<<1)|1;
			cn++;
			continue;
		}
		ii tr = d[id].front();
		if(tr.ss == 0) 
			a[i] = a[tr.ff]+1;
		else
			a[i] = a[tr.ff]-1;
		d[id].pop_front();
	}
	// for(int i = 0; i < (n<<1); ++i)
	// 	cout << a[i] << " ";
	// cout << endl;
	ll ans = 0;
	st.n = (n<<1);
	for(int i = 0; i < (n<<1); ++i){
		st.up(a[i]+1,1);
		ans += ((ll) st.ran(a[i]+2,n<<1));
	}
	return ans;
}

// int main(){
// 	cout << count_swaps({2,2,-2,-2,2,-2,2,-2}) << 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