Submission #424779

#	Time	Username	Problem	Language	Result	Execution time	Memory
424779		alireza_kaviani	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	97 ms	14376 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define SZ(x)			int((x).size())
#define all(x)			(x).begin() , (x).end()
#define sep				' '

const int MAXN = 2e5 + 10;

int n , fen[MAXN] , mark[MAXN];
vector<int> pos[MAXN];

void add(int x , int v){
	for(x++; x < MAXN ; x += x & -x)	fen[x] += v;
}

int get(int x){
	int ans = 0;
	for(x++ ; x > 0 ; x -= x & -x)	ans += fen[x];
	return ans;
}

ll count_swaps(vector<int> s) {
	n = SZ(s) / 2; ll ans = 0;
	for(int i = 0 ; i < n * 2 ; i++){
		s[i] += n; add(i , 1);
		pos[s[i]].push_back(i);
	}
	for(int i = 0 ; i < MAXN ; i++)	reverse(all(pos[i]));
	for(int i = 0 ; i < n * 2 ; i++){
		if(mark[i])	continue;
		int x = i , y = pos[n + n - s[i]].back();
		pos[s[i]].pop_back(); pos[n + n - s[i]].pop_back();
		mark[x] = mark[y] = 1;
//		cout << x << sep << y << sep << get(x) << sep << get(y) << endl;
		ans += get(y) - get(x) - (s[x] < s[y]);
		add(x , 1); add(y , -1);
	}
	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