제출 #299903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
299903		nhdtxdy	Arranging Shoes (IOI19_shoes)	C++17	85 / 100	1034 ms	48376 KiB

shoes

#include <bits/stdc++.h>
#define ll long long
#define FOR(i, x, y) for(int i = x; i <= y; ++i)
#define Size(v) (int)v.size()
#define pb push_back
#define eb emplace_back
using namespace std;

struct SegTree {
	int n;
	vector<int> st;
	SegTree(int n) {
		this->n = n;
		st.resize(4 * n + 1, 0);
	}
	void update(int pos, int val, int id, int u, int v) {
		if (pos < u || v < pos) return;
		if (u == v) {
			st[id] = val;
			return;
		}
		int mid = (u + v) / 2;
		update(pos, val, id * 2, u, mid);
		update(pos, val, id * 2 + 1, mid + 1, v);	
		st[id] = st[id * 2] + st[id * 2 + 1];
	}
	int query(int l, int r, int id, int u, int v) {
		if (l > r) return 0;
		if (r < u || v < l) return 0;
		if (l <= u && v <= r) return st[id];
		int mid = (u + v) / 2;
		int lv = query(l, r, id * 2, u, mid);
		int rv = query(l, r, id * 2 + 1, mid + 1, v);
		return (lv + rv);
	}
	void update(int pos, int val) {
		update(pos, val, 1, 1, n);
	}	
	int query(int l, int r) {
		return query(l, r, 1, 1, n);
	}
};

const int nax = 2e5 + 5;
map<int, int> pos, curr;
map<int, vector<int>> appear;
int mp[nax];
bool solved[nax], used[nax];

int64_t count_swaps(vector<int> a) {
	int n = Size(a);
	// cerr << "here1\n";
	SegTree st(n);
	// cerr << "?\n";
	for (int i = 1; i <= n; ++i) st.update(i, 1);
	// cerr << "here3\n";
	for (int i = 0; i < n; ++i) appear[a[i]].pb(i + 1);
	for (int i = 0; i < n; ++i) pos[a[i]] = i + 1;
	for (int i = 0; i < n; ++i)	mp[i + 1] = appear[-a[i]][curr[-a[i]]];
	for (int i = 0; i < n; ++i) {
		if (used[i + 1]) continue;
		used[i + 1] = true;
		mp[i + 1] = appear[-a[i]][curr[-a[i]]];
		++curr[a[i]], ++curr[-a[i]];
		used[mp[i + 1]] = true;
	}
	// cerr << "here2\n";
	int64_t res = 0;
	for (int i = 1; i <= n; ++i) {
		if (solved[i]) continue;
		solved[i] = true;
		int d = mp[i];
		solved[d] = true;
		if (a[i - 1] < 0) {
			res += st.query(i + 1, d - 1);
		}
		else res += st.query(i, d - 1);
		st.update(d, 0);
	}
	return res;
}

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