結果
問題 | No.252 "良問"(良問とは言っていない (2) |
ユーザー |
![]() |
提出日時 | 2015-07-24 23:41:49 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 229 ms / 2,000 ms |
コード長 | 2,314 bytes |
コンパイル時間 | 778 ms |
コンパイル使用メモリ | 83,860 KB |
実行使用メモリ | 20,644 KB |
最終ジャッジ日時 | 2024-07-16 00:27:25 |
合計ジャッジ時間 | 2,624 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:71:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 71 | scanf("%d",&T); | ~~~~~^~~~~~~~~
ソースコード
#include <cstdio>#include <cstdlib>#include <iostream>#include <string>#include <cmath>#include <algorithm>#include <vector>#include <queue>#include <stack>#include <map>#include <set>#include <cstring>typedef long long ll;using namespace std;#define mod 1000003#define INF 1000000000#define LLINF 2000000000000000000LL#define SIZE 100struct RMQ{int segn2,seg[2<<20];RMQ(){segn2=0;}void init(int n){segn2=1;while(segn2<n) segn2*=2;for(int i=0;i<segn2*2-1;i++)seg[i]=2147483647;}int q(int a,int b,int l=0,int r=-1,int k=0){if(r<0) r=segn2-1;if(a<=l && r<=b) return seg[k];if(r<a || b<l) return 2000000000;return min(q(a,b,l,(l+r)/2,k*2+1),q(a,b,(l+r)/2+1,r,k*2+2));}void set(int k,int x){k+=segn2-1;seg[k]=x;while(k>0){k=(k-1)/2;seg[k]=min(seg[k*2+1],seg[k*2+2]);}return;}};RMQ rmq2;int good[1000010];int probc[1000010];int main(){string S;int T,c,n,ans;scanf("%d",&T);for(int i=0;i<T;i++){ans = INF;cin >> S;n = (int)S.size();for(int i=0;i<n;i++){good[n]=INF;probc[i]=0;}rmq2.init(n);for(int j=0;j<n-3;j++){c=0;for(int i=0;i<4;i++){if(S[j+i]!="good"[i]){c++;}}good[j]=c;}for(int j=0;j<n-6;j++){c=0;for(int i=0;i<7;i++){if(S[j+i]!="problem"[i]){c++;}}if(c==0) probc[j+7]=1;rmq2.set(j,c);}for(int i=0;i<n-1;i++){probc[i+1]+=probc[i];}for(int i=0;i<n-10;i++){ans=min(ans,good[i]+rmq2.q(i+4,n-1)+probc[i]);}printf("%d\n",ans);}return 0;}