제출 #810199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
810199		fatemetmhr	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	61 ms	19724 KiB

shoes

// na mn tanha nistam


#include <bits/stdc++.h>
#include "shoes.h"

using namespace std;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
#define mp     make_pair

typedef long long ll;

const int maxn5 = 4e5 + 10;

vector <int> av[maxn5];
bool mark[maxn5];

namespace fen{
	int fen[maxn5];
	void add(int id, int val){
		for(++id; id < maxn5; id += id & -id)
			fen[id] += val;
	}

	int get(int id){
		int ret = 0;
		for(++id; id; id -= id & -id)
			ret += fen[id];
		return ret;
	}
}

long long count_swaps(std::vector<int> a) {
	int n = a.size();
	for(int i = n - 1; i >= 0; i--){
		fen::add(i, 1);
		av[a[i] + n + 4].pb(i);
	}
	ll ans = 0;
	for(int i = 0; i < n; i++) if(!mark[i]){
		av[a[i] + n + 4].pop_back();
		mark[i] = true;
		int j = av[(-a[i]) + n + 4].back();
		av[(-a[i]) + n + 4].pop_back();
		mark[j] = true;
		fen::add(i, -1);
		fen::add(j, -1);
		ans += fen::get(j);
		if(a[i] > 0)
			ans++;
	}
	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