結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー goodbatongoodbaton
提出日時 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);
      |     ~~~~~^~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#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 100
struct 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0