Submission #1326414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326414		JuanJL	Monochrome Points (JOI20_monochrome)	C++20	35 / 100	2096 ms	27356 KiB

monochrome

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;

ll n;

/*struct STree{
	ll n;
	vector<ll> st;
	STree(ll n):n(n),st(4*n+5) {}
	void upd(ll k , ll l, ll r, ll p, ll v){
		if(l+1==r){ st[k]=v; return; }
		ll mid = (l+r)/2;
		if(mid>p) upd(2*k,l,mid,p,v);
		else upd(2*k+1,mid,r,p,v);
		st[k]=st[2*k]+st[2*k+1];
	}
	ll qry(ll k, ll l, ll r, ll L, ll R){
		if(l>=R || r<=L) return 0;
		if(l>=L && r<=R) return st[k];
		ll mid = (l+r)/2;
		return qry(2*k,l,mid,L,R)+qry(2*k+1,mid,r,L,R);
	}
	void upd(ll p, ll v){ upd(1,0,n,p,v); }
	ll qry(ll l, ll r){ return qry(1,0,n,l,r); }
};*/

struct Fenwick{
	ll n;
	vector<ll> st;
	Fenwick(ll n):n(n),st(2*n+5){}
	void upd(ll p, ll v){
		while(p<=n){
			st[p]+=v;
			p+=p&-p;
		}
	}
	ll rqry(ll p){
		ll res = 0;
		while(p>=1){
			res+=st[p];
			p-=p&-p;
		}
		return res;
	}
	ll qry(ll l, ll r){
		return rqry(r)-rqry(l-1);
	}
};

vector<ll> b;
vector<ll> w;

ll solve(ll k){

	ll cnt = 0;
	vector<pair<pair<ll,ll>,ll>> line;

	forn(i,0,SZ(b)){
		ll j=k;
		line.pb({{b[i],w[j]},0});
		k++;
		k%=n;
	}
	
	forn(i,0,SZ(line)){
		line[i].snd=i;
		if(line[i].fst.fst>line[i].fst.snd)
			swap(line[i].fst.fst,line[i].fst.snd);
	}
	
	sort(ALL(line));

	vector<pair<ll,ll>> inp; forn(i,0,SZ(line)) inp.pb({line[i].fst.fst, i});
	vector<pair<ll,ll>> out; forn(i,0,SZ(line)) out.pb({line[i].fst.snd, i});
	
	sort(ALL(inp)); reverse(ALL(inp));
	sort(ALL(out)); reverse(ALL(out));
	
	Fenwick st(2*n); cnt=0;
	
	forn(i,0,2*n){
		while(!inp.empty() && inp.back().fst<=i){
			st.upd(inp.back().fst+1,1);
			inp.pop_back();
		}
		while(!out.empty() && out.back().fst<=i){
			cnt+=st.qry(line[out.back().snd].fst.fst+2, line[out.back().snd].fst.snd+1);
			st.upd(line[out.back().snd].fst.fst+1,(ll)-1);
			out.pop_back();
		}
	}

	return cnt;
}

int main(){ FIN;
	cin>>n;
	string s; cin>>s;

	
	
	forn(i,0,2*n){
		if(s[i]=='B'){
			b.pb(i);
		}else{
			w.pb(i);
		}
	}

	ll res = 0;
	
	ll l = 0; ll r=n-1;
	while(l<=r){
		ll mid1 = l+(r-l)/3;
		ll mid2 = r-(r-l)/3;

		ll c1 = solve(mid1);
		ll c2 = solve(mid2);

		if(c1<c2){
			l=mid1+1;
		}else{
			r=mid2-1;
		}

		res=max(res,max(c1,c2));
	}
	
	cout<<res<<'\n';
	return 0;
}

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