Submission #1052282

#TimeUsernameProblemLanguageResultExecution timeMemory
1052282MinbaevJJOOII 2 (JOI20_ho_t2)C++17
0 / 100
0 ms348 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast,unroll-loops") using namespace std; using namespace __gnu_pbds; #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define f first #define s second #define int long long #define ll long long #define pii pair<int,int> #define ar array template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;} template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;} template<class T> using st = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; const int inf = 1e17 + 7; const int mod = 1e9 + 7; const int N = 3e5 + 5; const int md = 998244353; int binpow(int a, int b){ if(b == 0)return 1; if(b % 2 == 0){ int c = binpow(a,b/2); return (c*c)%mod; } return (binpow(a,b-1)*a)%mod; } int divi(int a, int b){ return (a*(binpow(b,mod-2)))%mod; } int n,m,k; void solve(){ cin >> n >> m; string str, a; cin >> str; int pref[n][3]{}, last[n]{}; vector<vector<int>>v(3); vector<bool>flag(n); for(int i = 0;i<n;i++){ if(str[i] == 'J'){ pref[i][0] += 1; v[0].pb(i); } if(str[i] == 'O'){ pref[i][1] += 1; v[1].pb(i); } if(str[i] == 'I'){ pref[i][2] += 1; v[2].pb(i); } if(i > 0){ pref[i][0] += pref[i-1][0]; pref[i][1] += pref[i-1][1]; pref[i][2] += pref[i-1][2]; } } int mn = inf; for(int i = 0;i<n;i++){ if(str[i] == 'J'){ if(pref[i][0] >= m)last[i] = v[0][pref[i][0]-m]; } if(str[i] == 'O' && pref[i][1] >= m){ int l = 0, r = v[0].size()-1, ans = -1; while(l <= r){ int mid = (l+r)/2; if(v[0][mid] > v[1][pref[i][1]-2])r = mid - 1; else { ans = v[0][mid]; l = mid + 1; } } if(ans != -1 && pref[ans][0] >= m){ last[i] = last[ans]; flag[i] = true; } } if(str[i] == 'I' && pref[i][2] >= m){ int l = 0, r = v[1].size()-1, ans = -1; while(l <= r){ int mid = (l+r)/2; if(v[1][mid] > v[2][pref[i][2]-2])r = mid - 1; else { ans = v[1][mid]; l = mid + 1; } } if(ans != -1 && flag[ans]){ umin(mn, (i-last[ans]+1)-m*3); } //~ cout << ans << " "; } } cout << ((mn == inf) ? -1 : mn) << "\n"; //~ for(int i = 0;i<n;i++){ //~ cout << flag[i] << " " << last[i] << "\n"; //~ } } /* 5 4 35 100 70 70 45 15 80 40 20 95 20 50 0 10 10 0 60 60 0 0 100 0 */ signed main() { // freopen("seq.in", "r", stdin); // freopen("seq.out", "w", stdout); ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); int tt=1;//cin>>tt; while(tt--)solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...