Submission #514086

#	Time	Username	Problem	Language	Result	Execution time	Memory
514086		czhang2718	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	107 ms	10180 KiB

monochrome

#include "bits/stdc++.h"
using namespace std;

const int N=400001;
#define all(x) x.begin(), x.end()

int n;
string s;
long long ps[N];
int ind[N];
vector<int> black, white;

void solve(int i){
  // cout << "solve " << i << '\n';
  auto add=[&](int l, int r, int v){
    // cout << l << "-" << r << " add " << v << '\n';
    if(r<l) r+=n;
    ps[l]+=v;
    ps[r+1]-=v;
  };

  if(s[i]=='B'){
    auto pain=[&](int j)->int{
      return (ind[i]-j+n)%n;
    };
    // (i, i+m) 
    int cw1=*lower_bound(all(white), i);
    int cw2=*--upper_bound(all(white), i+n);
    if(cw1-i<=n){
      int l=ind[cw1%(2*n)], r=ind[cw2%(2*n)];
      add(pain(r), pain(l), -i);
      if(i>=n && cw2>=2*n){
        int k=*white.begin();
        add(pain(r), pain(ind[k]), 2*n);
      }
    }

    // (i+m ,i+n)
    if(upper_bound(all(white), i+n)==white.end()) return;
    int cc1=*upper_bound(all(white), i+n);
    int cc2=*--lower_bound(all(white), i+2*n);
    if(cc1<i+2*n){
      int l=ind[cc1%(2*n)], r=ind[cc2%(2*n)];
      add(pain(r), pain(l), i);
      if(i<n-1 && cc1<2*n){
        int k=*--lower_bound(all(white), 2*n);
        add(pain(ind[k]), pain(l), 2*n);
      }
    }
  } 
  else{
    auto pain=[&](int j)->int{
      return (j-ind[i]+n)%n;
    };
    // (i, i+m) 
    int cw1=*lower_bound(all(black), i);
    int cw2=*--lower_bound(all(black), i+n);
    // cout << cw1 << " " << cw2 << "\n";
    if(cw1-i<n){
      int l=ind[cw1%(2*n)], r=ind[cw2%(2*n)];
      add(pain(l), pain(r), -i);
    }

    // (i+m ,i+n)
    int cc1=*lower_bound(all(black), i+n);
    int cc2=*--lower_bound(all(black), i+2*n);
    if(cc1<i+2*n){
      int l=ind[cc1%(2*n)], r=ind[cc2%(2*n)];
      add(pain(l), pain(r), i);
    }
  }
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> s;
  s+=s;
  int w=0, b=0;
  for(int i=0; i<2*n; i++){
    if(s[i]=='W'){
      ind[i]=w;
      w++;
    }
    else{
      ind[i]=b;
      b++;
    }
  }
  for(int i=0; i<4*n; i++){
    if(s[i%(2*n)]=='W') white.push_back(i);
    else black.push_back(i);
  }
  for(int i=0; i<2*n; i++) solve(i);
  for(int i=1; i<2*n; i++) ps[i]+=ps[i-1];
    
  long long ans=0;
  for(int i=0; i<n; i++){
    // cout << ps[i]+ps[i+n]-n << "\n";
    ans=max(ans, ps[i]+ps[i+n]);
  }
  cout << (ans-n)/2;
}

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