제출 #889994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
889994		avighna	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	16 ms	7244 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

#define ll long long

struct Node {
  ll j, o, i, idx;

  Node() {}
  Node(ll j, ll o, ll i, ll idx) : j(j), o(o), i(i), idx(idx) {}
};

const ll N = 2e5;

Node x[N + 1];

ll find_where_appears(char c, ll k, ll st, ll en) {
  ll ost = st;
  ll ans = en + 1;
  while (st <= en) {
    ll m = (st + en) / 2;
    ll val;
    if (c == 'J') {
      val = x[m].j - x[ost - 1].j;
    } else if (c == 'O') {
      val = x[m].o - x[ost - 1].o;
    } else {
      val = x[m].i - x[ost - 1].i;
    }
    if (val >= k) {
      ans = m;
      en = m - 1;
    } else {
      st = m + 1;
    }
  }
  return ans;
}

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

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

  s = " " + s;
  x[0].j = x[0].o = x[0].i = x[0].idx = 0;
  for (ll i = 1; i <= n; ++i) {
    x[i] = x[i - 1];
    x[i].j += s[i] == 'J';
    x[i].o += s[i] == 'O';
    x[i].i += s[i] == 'I';
    x[i].idx = i;
  }

  ll ans = LLONG_MAX;

  for (ll j = 1; j <= n; ++j) {
    if (s[j] != 'J') {
      continue;
    }
    ll idx = find_where_appears('J', k, j, n);
    idx = find_where_appears('O', k, idx, n);
    idx = find_where_appears('I', k, idx, n);
    if (idx == n + 1) {
      continue;
    }
    ans = min(ans, idx - j + 1 - 3 * k);
  }

  if (ans == LLONG_MAX) {
    cout << "-1\n";
  } else {
    cout << ans << "\n";
  }
}

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