Submission #231689

#	Time	Username	Problem	Language	Result	Execution time	Memory
231689		Haunted_Cpp	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	29 ms	3212 KiB

ho_t2

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

#pragma GCC optimize ("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  string w;
  cin >> w;
  vector<int> prefix_j (n);
  vector<int> prefix_i (n);
  
  for (int i = 0; i < n; i++) {
    prefix_j[i] = (w[i] == 'J');
    prefix_i[i] = (w[i] == 'I');
    if (i) {
      prefix_j[i] += prefix_j[i - 1];
      prefix_i[i] += prefix_i[i - 1];
    }
  }
  prefix_j.emplace_back(prefix_j.back());
  prefix_i.emplace_back(prefix_i.back());
  auto range_sum = [&] (int lo, int hi, vector<int> &prefix) {
    return prefix[hi] - (lo - 1 >= 0 ? prefix[lo - 1] : 0);
  };
  auto upper = [&] (int lo, int hi, vector<int> &prefix) {
    if (range_sum(lo, hi, prefix) < k) {
      return (int) 1e9;
    }
    int inicio = lo;
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      if (range_sum(inicio, mid, prefix) >= k) hi = mid;
      else lo = mid + 1;
    }
    return hi;
  };
  auto lower = [&] (int lo, int hi, vector<int> &prefix) {
    if (range_sum(lo, hi, prefix) < k) {
      return (int) 1e9;
    }
    int inicio = hi;
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2 + 1; 
      if (range_sum(mid, inicio, prefix) >= k) lo = mid;
      else hi = mid - 1;
    }
    return lo;
  };
  int lo = 0;
  int cnt = 0;
  int mn = 1e9;
  for (int hi = 0; hi < n; hi++) {
    cnt += (w[hi] == 'O');
    // Remover extra
    while (cnt > k) {
      cnt -= (w[lo] == 'O');
      ++lo;
    }
    // Ajustar janela
    while (w[lo] != 'O') {
      ++lo;
    }
    if (cnt == k) {
      int menor = lower (0, lo - 1, prefix_j);
      int maior = upper (hi + 1, n, prefix_i);
      if (menor > 1e7 || maior > 1e7) continue;
      int cur = (maior - menor + 1) - (k * 3);
      mn = min (mn, cur);
    }
  }
  cout << (mn > 1e7 ? -1 : mn) << '\n';
  return 0;
}

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