제출 #1206033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206033		vidux	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	218 ms	26252 KiB

shoes

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

//#define LOCAL

#define FOR(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n, m) for (int i = n; i <= m; ++i)
#define REPR(i, n, m) for (int i = n; i >= m; --i)
#define FORR(x, a) for (auto& x : a)
#define FORR2(x, y, a) for (auto& [x, y] : a)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(a) ((int)a.size())

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

const int INF = 1e9;
const ll LLINF = 1e18;
const int N = 1e5;

int n;
vi t;
void build() {
	t = vi(2*n, 1);
	for (int i = n-1; i > 0; i--) t[i] = t[i*2]+t[i*2+1];
}
void change(int i, int v) {
	for (t[i+=n] = v; i > 1; i >>= 1) t[i>>1] = t[i] + t[i^1];
}
int query(int l, int r) {
	int ans = 0;
	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if (l&1) ans += t[l++];
		if (r&1) ans += t[--r];
	}
	return ans;
}

ll count_swaps(vi a) {
	n = SZ(a);
    ll ans = 0;
	map<int, vi> mp;
	FOR(i, n) mp[a[i]].push_back(i);
	FORR2(x, v, mp) reverse(ALL(v));
	vi seen(n);
	build();
	FOR(i, n) {
		if (seen[i]) continue;
		if (a[i] > 0) ans++;
		while (seen[mp[-a[i]].back()]) mp[-a[i]].pop_back();
		int j = mp[-a[i]].back();
		seen[j] = 1;
		change(j, 0);
		seen[i] = 1;
		change(i, 0);
		//cout << i << " " << j << ": " << query(i, j) << endl;
		ans += query(i, j);
	}
    return ans;
}

#ifdef LOCAL
int main() {
	cout << count_swaps({-2, 2, 2, -2, -2, 2});
	cout << count_swaps({2, 1, -1, -2});

    return 0;
}
#endif

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