Submission #202879

#	Time	Username	Problem	Language	Result	Execution time	Memory
202879		EntityIT	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	110 ms	3204 KiB

ho_t2

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }

const int inf = 1e9;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

map<char, int> label{ { 'J', 0 }, { 'O', 1 }, { 'I', 2 } };

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  int n, k; string s; cin >> n >> k >> s;

  vector<array<int, 3> > pref(n + 1);
  for (int i = 0; i < n; ++i) {
    pref[i + 1] = pref[i];
    ++pref[i + 1][ label[ s[i] ] ];
  }
  auto get = [&](int be, int en, char c) { return pref[en][ label[c] ] - pref[be][ label[c] ]; };

  auto findPos = [&](int i, char c) {
    int l = i, r = n;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (get(i, mid + 1, c) >= k) r = mid;
      else l = mid + 1;
    }
    return l;
  };

  int ans = inf;
  for (int i = 0; i < n; ++i) {
    int j = findPos(findPos(findPos(i, 'J'), 'O'), 'I');
    if (j < n) asMn(ans, j - i + 1 - 3 * k);
  }

  cout << (ans == inf ? -1 : ans) << '\n';

  return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87