oj.uz

Submission #544650

# Submission time Handle Problem Language Result Execution time Memory
544650 2022-04-02T14:13:05 Z pokmui9909 공장 (KOI13_factory) C++17
20 / 20
 348 ms 35320 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16744 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 9 ms 16868 KB Output is correct
4 Correct 11 ms 17876 KB Output is correct
5 Correct 9 ms 18516 KB Output is correct

Subtask #2
3.4 / 3.4

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19796 KB Output is correct
2 Correct 13 ms 24148 KB Output is correct
3 Correct 16 ms 24660 KB Output is correct

Subtask #3
3.8 / 3.8

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25152 KB Output is correct
2 Correct 41 ms 25580 KB Output is correct
3 Correct 55 ms 26044 KB Output is correct

Subtask #4
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 67 ms 26580 KB Output is correct
2 Correct 105 ms 27864 KB Output is correct
3 Correct 132 ms 28812 KB Output is correct
4 Correct 199 ms 30948 KB Output is correct

Subtask #5
5.8 / 5.8

# Verdict Execution time Memory Grader output
1 Correct 262 ms 33076 KB Output is correct
2 Correct 257 ms 35152 KB Output is correct
3 Correct 244 ms 35288 KB Output is correct
4 Correct 342 ms 35164 KB Output is correct
5 Correct 348 ms 35260 KB Output is correct
6 Correct 340 ms 35320 KB Output is correct