Submission #1159415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159415		Der_Vlapos	Monochrome Points (JOI20_monochrome)	C++20	35 / 100	626 ms	12660 KiB

monochrome

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define f first
#define s second
#define all(v) v.begin(), v.end()

// #define int ll

const int mod1 = 1e9 + 7;
const int mod2 = 998244353;

int dp1[1003][1003];
int dp2[1003][1003];

struct segTreeSum
{
	vector<ll> tree;
	int sz;

	void init(int n)
	{
		sz = n;
		tree.resize(2 * sz);
	}

	void build(vector<int> &a)
	{
		init(a.size());
		for (int i = 0; i < a.size(); ++i)
			tree[i + sz] = a[sz];

		for (int i = sz - 1; i > 0; --i)
			tree[i] = tree[i << 1] + tree[(i << 1) + 1];
	}

	int get(int l, int r) // [l, r)
	{
		l += sz;
		r += sz;
		int res = 0;

		while (l < r)
		{
			if (l & 1)
				res += tree[l++];
			if (r & 1)
				res += tree[--r];
			l >>= 1;
			r >>= 1;
		}

		return res;
	}

	void add(int pos, int val)
	{
		pos += sz;
		tree[pos] += val;
		pos >>= 1;
		while (pos)
		{
			tree[pos] = tree[pos << 1] + tree[(pos << 1) + 1];
			pos >>= 1;
		}
	}
};

struct test
{
	vector<int> b, w;
	vector<int> dp;
	int n;

	int solve(int k)
	{
		if (dp[k] != -1)
			return dp[k];
		segTreeSum tree;
		tree.init(2 * n);
		vector<pii> segs;
		for (int i = 0; i < n; ++i)
			segs.pb({min(b[i], w[(i + k) % n]), max(b[i], w[(i + k) % n])});

		sort(all(segs), [](pii a, pii b)
			 { return a.s < b.s; });
		int cnt = 0;
		for (int i = 0; i < n; ++i)
		{
			auto [l, r] = segs[i];
			cnt += tree.get(0, l + 1);
			tree.add(l, 1);
			tree.add(r, -1);
		}
		return dp[k] = cnt;
	}

	void solve()
	{
		cin >> n;
		dp.resize(n, -1);
		for (int i = 0; i < 2 * n; ++i)
		{
			char x;
			cin >> x;
			if (x == 'B')
				b.pb(i);
			else
				w.pb(i);
		}
		int res = 0;

		bool inverted = 0;
		if (solve(n - 1) > solve(1))
			inverted = 1;

		// for (int i = 0; i < n; ++i)
		// {
		// 	cout << solve(i) << " ";
		// }
		// cout << "\n";

		int L = 0, R = n;
		auto getV = [&](int x) -> int
		{ return inverted ? ((n - 1 - x + n) % n) : ((x + n) % n); };
		while ((R - L) > 1)
		{
			// cerr << L << " " << R << "\n";
			int M = (L + R) >> 1;

			int val = solve(getV(M));
			if (val < solve(getV(0)))
				R = M;
			else if (solve(getV(M - 1)) <= val)
				L = M;
			else
				R = M;
		}

		cout << solve(getV(L)) << "\n";
	}
};

main()
{
	test t;
	t.solve();
}

Compilation message (stderr)

monochrome.cpp:148:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  148 | main()
      | ^~~~

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 10 / 10
• Subtask 4: 0 / 65