Submission #292589

#	Time	Username	Problem	Language	Result	Execution time	Memory
292589		Pajaraja	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	166 ms	4240 KiB

monochrome

#include <bits/stdc++.h>
#define MAXN 200007
using namespace std;
vector<int> b,w;
int dx[MAXN],dy[MAXN],n;
long long val(int x)
{
	long long solc=0;
	int k=x,p=x;
	for(int i=0;i<x;i++)
	{
		while(w[k-x]<b[i] && k<n) k++;
		while(b[p]<w[n-x+i] && p<n) p++;
		solc+=(n-max(k,p)+min(k,p)-x);
	}
	k=0;
	for(int i=0;i<x;i++) 
	{
		while(w[n-x+k]<b[i]) k++;
		solc+=(i-k);
	}
	k=x;
	for(int i=x;i<n;i++) 
	{
		while(b[k]<w[i-x]) k++;
		solc+=(i-k);
	}
	return solc;
}
bool validl(int x)
{
	for(int i=0;i<x;i++) {dx[i]=b[i]; dy[i]=w[n-x+i];}
	for(int i=x;i<n;i++) {dx[i]=b[i]; dy[i]=w[i-x];}
	for(int i=0;i<x;i++) if(dx[i]>dy[i]) return false;
	return true;
}

bool validr(int x)
{
	for(int i=0;i<x;i++) {dx[i]=b[i]; dy[i]=w[n-x+i];}
	for(int i=x;i<n;i++) {dx[i]=b[i]; dy[i]=w[i-x];}
	for(int i=x;i<n;i++) if(dx[i]<dy[i]) return false;
	return true;
}
int main()
{
	string s;
	cin>>n; cin>>s;
	for(int i=0;i<2*n;i++) 
	{
		if(s[i]=='W') w.push_back(i);
		else b.push_back(i);
	}
	long long sol=0;
	int r=n,l=0,rzl,rzr;
	while(l!=r)
	{
		int s=(l+r)/2;
		if(validr(s)) r=s;
		else l=s+1;
	}
	rzl=l;
	r=n; l=0;
	while(l!=r)
	{
		int s=(l+r+1)/2;
		if(validl(s)) l=s;
		else r=s-1;
	}
	rzr=r;
	l=rzl; r=rzr;
	while(r-l>3)
	{
		int s1=(l+r)/2-1;
		int s2=(l+r)/2+1;
		int x=val(s1),y=val(s2);
		if(x<y) l=s1;
		else r=s2;
	}
	for(int i=l;i<=r;i++) sol=max(sol,val(i));
	cout<<sol;
}

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