Submission #901271

#	Time	Username	Problem	Language	Result	Execution time	Memory
901271		Keys	Monochrome Points (JOI20_monochrome)	C++14	100 / 100	1726 ms	14276 KiB

monochrome

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
typedef vector<int> vi;
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (a); i >= (b); i--)
#define all(x) x.begin(), x.end()
#define f first
#define s second

struct ft {
    vector<int> bit; int n;
    ft(int _n) {bit.resize(_n + 5); n = _n + 5;}
    void upd(int i, int x) {i += 2; for (;i < n; i += i & (-i)) bit[i] += x;}
    int query(int i) {i += 2; int x = 0; for(; i > 0; i -= i & (-i)) x += bit[i]; return x;}
    int query(int i, int j) {if (i > j) return 0; return query(j) - query(i - 1);}
};

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n; string s; cin >> s;
  vi b, w; FOR(i, 0, 2 * n) {
    if (s[i] == 'B') b.pb(i);
    else w.pb(i);
  }
  auto calc = [&] (vi l, vi r) {
    ft f(2 * n + 5);
    vi ord(n); iota(all(ord), 0);
    int ans = 0;
    FOR(i, 0, n) if (r[i] < l[i]) swap(r[i], l[i]);
    sort(all(ord), [&] (int u, int v) {return l[u] < l[v];});
    FOR(j, 0, n) {
      int i = ord[j];
      ans += f.query(l[i], r[i]);
      f.upd(l[i], -1); f.upd(r[i], 1);
    }
    return ans;
  };
  auto solve = [&] (int r) {
    vi tb = b;
    rotate(tb.begin(), tb.begin() + r, tb.end());
    return calc(tb, w);
  };
  int lo = 0, hi = n - 1;
  while (lo < hi) {
    int m = (lo + hi) / 2;
    if (solve(m) < solve(m + 1)) lo = m + 1;
    else hi = m;
  }
  cout << solve(lo) << endl;
}

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