# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
423368 | 2021-06-11T03:30:46 Z | juggernaut | JJOOII 2 (JOI20_ho_t2) | C++17 | 1 ms | 204 KB |
#include<bits/stdc++.h> #define fr first #define sc second using namespace std; void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);} typedef long long ll; #define USING_ORDERED_SET 0 #if USING_ORDERED_SET #include<bits/extc++.h> using namespace __gnu_pbds; template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; #endif template<class T>void umax(T &a,T b){if(a<b)a=b;} template<class T>void umin(T &a,T b){if(b<a)a=b;} #ifdef IOI2021SG #define printl(args...)printf(args) #else #define printl(args...)((void)0) #endif int n,k; string s; int pref[200005][3]; int main(){ //ios_base::sync_with_stdio(0); //cin.tie(0); cin>>n>>k>>s; s=" "+s; for(int i=1;i<=n;i++){ pref[i][0]=pref[i-1][0]+(s[i]=='J'); pref[i][1]=pref[i-1][1]+(s[i]=='O'); pref[i][2]=pref[i-1][2]+(s[i]=='I'); } int mn=1e9; for(int i=1;i<=n;i++){ int pivot=i-1; int l=i; int r=n; while(l<r){ int mid=(l+r)>>1; if(pref[mid][0]-pref[pivot][0]>=k)r=mid; else l=mid+1; } if(pref[l][0]-pref[pivot][0]<k)continue; r=n; pivot=l-1; while(l<r){ int mid=(l+r)>>1; if(pref[mid][1]-pref[pivot][1]>=k)r=mid; else l=mid+1; } if(pref[l][1]-pref[pivot][1]<k)continue; r=n; pivot=l-1; while(l<r){ int mid=(l+r)>>1; if(pref[mid][2]-pref[pivot][2]>=k)r=mid; else l=mid+1; } if(pref[l][2]-pref[i-1][2]<k)continue; umin(mn,l-i+1); } if(mn==int(1e9))puts("-1"); else printf("%d",mn-3*k); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
7 | Incorrect | 1 ms | 204 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
7 | Incorrect | 1 ms | 204 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 0 ms | 204 KB | Output is correct |
7 | Incorrect | 1 ms | 204 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |