Submission #292622

#	Time	Username	Problem	Language	Result	Execution time	Memory
292622		kdh9949	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	936 ms	8708 KiB

monochrome

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define x first
#define y second
#define all(v) v.begin(),v.end()

namespace BIT {
  int n;
  vint d;
  void i(int n_) { n = n_; d = vint(n + 1); }
  void u(int x, int v){ for(x++; x <= n; x += x & -x) d[x] += v; }
  int g(int x){ int r = 0; for(x++; x; x &= x - 1) r += d[x]; return r; }
  int g(int s, int e) { return g(e) - g(s - 1); }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  string s;
  cin >> n >> s;

  vint w, b;
  for(int i = 0; i < 2 * n; i++) (s[i] == 'W' ? w : b).push_back(i);

  ll ans = 0;
  vll memo(n, -1LL);
  auto f = [&](int t) {
    if(memo[t] >= 0) return memo[t];

    vint mat(2 * n);
    for(int i = 0; i < n; i++) {
      int A = w[i], B = b[(i + t) % n];
      mat[A] = B;
      mat[B] = A;
    }

    BIT::i(2 * n);
    ll cur = 0;
    for(int i = 0; i < 2 * n; i++) {
      if(i < mat[i]) BIT::u(i, 1);
      else {
        cur += BIT::g(mat[i] + 1, i - 1);
        BIT::u(mat[i], -1);
      }
    }

    ans = max(ans, cur);
    return memo[t] = cur;
  };

  if(n <= 4000) {
    for(int i = 0; i < n; i++) f(i);
    cout << ans << '\n';
  }
  else {
    int st = (f(0) < f(1));
    int en = (f(n - 2) < f(n - 1));
    if(st != en) {
      int l = 0, r = n - 2;
      while(l < r) {
        int m = (l + r + 1) / 2;
        if(f(m) < f(m + 1)) l = m;
        else r = m - 1;
      }
    }
    else if(st == 0) {
      int l = 0, r = n - 2;
      for(; ; l += (n / 20)) if(f(l) < f(l + 1)) break;
      while(l < r) {
        int m = (l + r + 1) / 2;
        if(f(m) < f(m + 1)) l = m;
        else r = m - 1;
      }
    }
    else{
      int l = 0, r = n - 2;
      for(; ; r -= (n / 20)) if(f(r) >= f(r + 1)) break;
      while(l < r) {
        int m = (l + r + 1) / 2;
        if(f(m) < f(m + 1)) l = m;
        else r = m - 1;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

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