Submission #996751

#TimeUsernameProblemLanguageResultExecution timeMemory
996751cotJJOOII 2 (JOI20_ho_t2)C++14
0 / 100
0 ms344 KiB
#include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <set> #define int long long #define ff first #define ss second #define pb push_back #define pp pop_back #define all(x) x.begin(),x.end() #define pii pair<int,int> #define r0 return 0 using namespace std; const int N = 3 * 1e5 + 5, M = 55, MOD = 998244353; int n,m,k,l,r,q,cur,pos1,pos2,ans; string s; int pref1[N],pref2[N],pref3[N]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; cin >> s; s = " " + s; for (int i = 1; i <= n; i++) { pref1[i] = pref1[i - 1] + (s[i] == 'J'); pref2[i] = pref2[i - 1] + (s[i] == 'O'); pref3[i] = pref3[i - 1] + (s[i] == 'I'); } ans = 1e9; for (int i = 4; i <= 4; i++) { if (s[i] != 'J') continue; int l = 1,r = i; pos1 = 1e9; while (l <= r) { int mid = (l + r) / 2; if (pref1[i] - pref1[mid - 1] >= k) { pos1 = mid; l = mid + 1; } else { r = mid - 1; } } if (pos1 == 1e9) continue; // cout << 1 << endl; cur = 1e9; l = i; r = n; while (l <= r) { int mid = (l + r) / 2; if (pref2[mid] - pref2[i - 1] >= k) { cur = mid; r = mid - 1; } else { l = mid + 1; } } if(cur == 1e9) continue; // cout << 2 << endl; pos2 = 1e9; l = cur; r = n; while (l <= r) { int mid = (l + r) / 2; if (pref3[mid] - pref3[cur - 1] >= k) { pos2 = mid; r = mid - 1; } else { l = mid + 1; } } if (pos2 == 1e9) continue; // cout << 3 << endl; ans = min(ans,pos2 - pos1 + 1 - 3 * k); } if (ans == 1e9) { cout << -1 << endl; } else { cout << ans << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...