Submission #627714

#	Time	Username	Problem	Language	Result	Execution time	Memory
627714		Abrar_Al_Samit	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	24 ms	3124 KiB

ho_t2

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

const int MX = 2e5 + 5;

int prej[MX], preo[MX], prei[MX];

int get(int l, int r, int *a) {
  if(l>r) return 0;
  return a[r] - a[l-1];
}
string s;
void PlayGround() {
  int n, k;
  cin>>n>>k;
  cin>>s;
  s = "$" + s;

  for(int i=1; i<=n; ++i) {
    if(s[i]=='J') prej[i] = 1;
    else if(s[i]=='O') preo[i] = 1;
    else prei[i] = 1;

    prej[i] += prej[i-1];
    preo[i] += preo[i-1];
    prei[i] += prei[i-1];
  }

  int ans = INT_MAX;
  for(int i=1; i<=n; ++i) {
    int j = i;
    if(get(j, n, prej)<k) break;
    int l = i, r = n;
    while(l<r) {
      int mid = (l+r)/2;
      if(get(j, mid, prej)>=k) r = mid;
      else l = mid+1;
    }
    ++l, r = n, j = l;
    if(get(j, n, preo)<k) break;
    while(l<r) {
      int mid = (l+r)/2;
      if(get(j, mid, preo)>=k) r = mid;
      else l = mid+1;
    }
    ++l, r = n, j = l;
    if(get(j, n, prei)<k) break;
    while(l<r) {
      int mid = (l+r)/2;
      if(get(j, mid, prei)>=k) r = mid;
      else l = mid+1;
    }
    ans = min(ans, l-i+1 - k*3);
  }
  if(ans==INT_MAX) ans = -1;
  cout<<ans<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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