Submission #900777

#	Time	Username	Problem	Language	Result	Execution time	Memory
900777		Keys	Monochrome Points (JOI20_monochrome)	C++14	35 / 100	2045 ms	14300 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;
  };
  vi l(n);
  for (int i = 0; i < n; i++) {
    l[i] = calc(b, w);
    rotate(b.begin(), b.begin() + 1, b.end());
  }
  cout << *max_element(all(l)) << endl;
}

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