Submission #1255486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255486		Seyyed_Mojtaba_Mortazavi	Monochrome Points (JOI20_monochrome)	C++20	35 / 100	338 ms	5304 KiB

monochrome

#include <bits/stdc++.h>

using namespace std;

#define int long long int
typedef pair <int, int> pii;

const int MAXN = 2e5 + 10;

vector <int> W;
vector <int> B;
vector <pii> seg;

struct Fenwick {

	int node[MAXN];

	void update(int n, int ind, int val)
	{
		for (; ind <= n; ind += ind & -ind)
			node[ind] += val;
	}

	int get(int ind)
	{
		int res = 0;
		for (; ind; ind -= ind & -ind)
			res += node[ind];
		return res;
	}

	int get(int l, int r)
	{
		return get(r) - get(l - 1);
	}

} Fen;

bool cmp(pii x, pii y)
{
	return x.second < y.second;
}

signed main()
{
	int n, ans = 0;
	cin >> n;
	for (int i = 1; i <= 2 * n; i++)
	{
		char c;
		cin >> c;
		if (c == 'W')
			W.push_back(i);
		else
			B.push_back(i);
	}
	for (int i = 1; i <= n; i++)
	{
		seg.clear();
		memset(Fen.node, 0, sizeof(Fen.node));
		for (int j = 0; j < n; j++)
		{
			int v = B[j];
			int u = W[(j + i) % n];
			seg.push_back({min(v, u), max(v, u)});
			Fen.update(2 * n, min(v, u), +1);
		}
		sort(seg.begin(), seg.end(), cmp);
		int tmp = 0;
		for (int j = 0; j < n; j++)
		{
			Fen.update(2 * n, seg[j].first, -1);
			tmp += Fen.get(seg[j].first, seg[j].second);
		}
		ans = max(ans, tmp);
	}
	cout << ans << endl;
}

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