Submission #1159308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159308		Der_Vlapos	Monochrome Points (JOI20_monochrome)	C++20	35 / 100	2094 ms	11804 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
{
	void solve()
	{
		int n;
		cin >> n;
		vector<int> b, w;
		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;
		for (int k = 0; k < n; ++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);
			}
			res = max(res, cnt);
		}

		cout << res << "\n";
	}
};

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

Compilation message (stderr)

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

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