Submission #293633

#	Time	Username	Problem	Language	Result	Execution time	Memory
293633		errorgorn	Monochrome Points (JOI20_monochrome)	C++14	0 / 100	3 ms	3456 KiB

monochrome

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int fen[400005];

void upd(int i){
	while (i<400005){
		fen[i]++;
		i+=i&-i;
	}
}

int query(int i){
	int res=0;
	while (i){
		res+=fen[i];
		i-=i&-i;
	}
	return res;
}

int query(int i,int j){
	return query(j)-query(i);
}

ii mp(int i,int j){
	if (i<j) return ii(i,j);
	else return ii(j,i);
}

int n;
string s;
vector<int> b,w;

int eval(int x){
	memset(fen,0,sizeof(fen));
	vector<ii> edge;
		
	rep(y,0,n) edge.push_back(mp(b[y],w[(x+y)%n]));
	
	ll curr=0;
	for (auto &it:edge){
		curr+=query(it.fi,it.se);
		upd(it.se);
	}
	
	return curr;
}

int solve(int l,int r){
	int m1,m2;
	
	while (r-l>3){
		m1=(r+l)>>1;
		m2=m1+1;
		
		if (eval(m1)>eval(m2)) r=m1;
		else l=m2;
	}
	
	int ans=0;
	rep(x,l,r+1) ans=max(ans,eval(x));
	return ans;
}

main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n;
	cin>>s;
	
	rep(x,0,2*n){ //so im gonna 1 index because fenwick
		if (s[x]=='B') b.push_back(x+1);
		else w.push_back(x+1);
	}
	
	if (n==1) cout<<0<<endl;
	else{
		int ans=0;
		
		int curr=0;
		int inc=max(n/2+5,1LL);
		while (curr<n){
			ans=max(ans,solve(curr,min(curr+inc-1,n-1)));
			curr+=inc;
		}
		
		cout<<ans<<endl;
	}
}

Compilation message (stderr)

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

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