Submission #1326405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326405		JuanJL	Monochrome Points (JOI20_monochrome)	C++20	35 / 100	2095 ms	33592 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))
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); }
};

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

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

	ll res = 0;
	
	forn(k,0,n){
		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));
		
		STree st(2*n); cnt=0;

		forn(i,0,2*n){
			while(!inp.empty() && inp.back().fst<=i){
				st.upd(inp.back().fst,1);
				inp.pop_back();
			}
			while(!out.empty() && out.back().fst<=i){
				cnt+=st.qry(line[out.back().snd].fst.fst+1, line[out.back().snd].fst.snd+1);
				st.upd(line[out.back().snd].fst.fst,(ll)0);
				out.pop_back();
			}
		}
		res=max(res,cnt);
	}
	
	cout<<res<<'\n';
	
	return 0;
}

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