Submission #591230

#	Time	Username	Problem	Language	Result	Execution time	Memory
591230		AriaH	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	1760 ms	6432 KiB

monochrome

/* Ignore Others Only Focus On Yourself! */
/* Im the Best! */

#pragma GCC optimize("O3")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;

const int N = 4e5 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

mt19937 rng(time(nullptr));

int n, fen[N];

void add(int i, int x)
{
	for(i += 3; i < N; i += i & -i)
	{
		fen[i] += x;
	}
}

int get(int i, int ret = 0)
{
	for(i += 3; i; i -= i & -i)
	{
		ret += fen[i];
	}
	return ret;
}

string s;

vector < int > W, B;

vector < pii > seg;

ll tot;

ll solve(int Shift)
{
	ll ret = 0;
	memset(fen, 0, sizeof fen);
	seg.clear();
	for(int i = 0; i < n; i ++)
	{
		int j = (i + Shift) % n;
		seg.push_back(Mp(max(W[i], B[j]), min(W[i], B[j])));
	}
	sort(all(seg));
	for(int i = 0; i < n; i ++)
	{
		int l = seg[i].S;
		int now = get(l) - (lower_bound(all(seg), Mp(l + 1, -1)) - seg.begin());
		ret += now;
		add(l, 1);
	}
	tot = max(tot, ret);
	return ret;
}

int main()
{
	fast_io;
	cin >> n >> s;
	for(int i = 0; i < n << 1; i ++)
	{
		if(s[i] == 'W')
		{
			W.push_back(i);
		}
		else
		{
			B.push_back(i);
		}
	}
	int l = 0, r = n - 1;
	solve(0);
	solve(n - 1);
	while(r - l > 20)
	{
		int l1 = (l * 2 + r) / 3, l2 = (r * 2 + l) / 3;
		ll L = solve(l1), R = solve(l2);
		if(L < R)
		{
			l = l1;
		}
		else
		{
			r = l2;
		}
	}
	for(int i = l; i <= r; i ++)
	{
		solve(i);
	}
	cout << tot;
	return 0;
}

/* check corner case(n = 1?), watch for negetive index or overflow */

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