Submission #544650

#	Time	Username	Problem	Language	Result	Execution time	Memory
544650		pokmui9909	공장 (KOI13_factory)	C++17	20 / 20	348 ms	35320 KiB

factory

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

using ll = long long;
const ll S = (1 << 20);
ll n;
ll A[500005];
ll mp[1000005];

class SegTree
{
public:
	void update(ll k, ll v) { update(1, 1, S, k, v); }
	ll query(ll l, ll r) { return query(1, 1, S, l, r); }

	void update(ll node, ll s, ll e, ll k, ll v)
	{
		if (s == e)
		{
			T[node] = v;
			return;
		}
		ll m = (s + e) / 2;
		ll lch = node * 2, rch = node * 2 + 1;
		if (k <= m) update(lch, s, m, k, v);
		else update(rch, m + 1, e, k, v);
		T[node] = T[lch] + T[rch];
	}

	ll query(ll node, ll s, ll e, ll l, ll r)
	{
		if (e < l || s > r) return 0;
		if (l <= s && e <= r) return T[node];
		ll m = (s + e) / 2;
		ll lch = node * 2, rch = node * 2 + 1;
		ll x = query(lch, s, m, l, r), y = query(rch, m + 1, e, l, r);
		return x + y;
	}
private:
	ll T[2 * S] = {};

};

signed main()
{
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> n;
	SegTree ST;
	for (ll i = 1; i <= n; i++)
	{
		ll k; cin >> k;
		mp[k] = i;
	}
	for (ll i = 1; i <= n; i++)
	{
		ll k; cin >> k;
		A[i] = mp[k];
	}
	ll inv = 0;
	for (ll i = 1; i <= n; i++)
	{
		inv += ST.query(A[i] + 1, n);
		ST.update(A[i], 1);
	}
	cout << inv;
}

// 2 4 1 3 5

• Subtask 1: 2.2 / 2.2
• Subtask 2: 3.4 / 3.4
• Subtask 3: 3.8 / 3.8
• Subtask 4: 4.8 / 4.8
• Subtask 5: 5.8 / 5.8