QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#137459 | #2353. Maharajas are Going Home | S_Explosion# | Compile Error | / | / | Python3 | 1.1kb | 2023-08-10 12:56:07 | 2023-08-10 12:56:10 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-08-10 12:56:10]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-08-10 12:56:07]
- 提交
answer
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll p=1e9+7;
int o,k,ls,lp,cnt[250005];
ll ans,hshs[250005],hshp[250005],pw[250005];
char S[250005],P[250005];
void init(char S[],ll hsh[],int n){
for(int i=1;i<=n;i++)
hsh[i]=(hsh[i-1]*2+(S[i]=='o'))%p;
}
int solve(int i,int pos){
int l=pos,r=lp,mid,res;
while(l<=r){
mid=(l+r)>>1;
if(hshs[i+mid-1]-hshs[pos-1]*pw[lp]==hshp[mid]-hsh[pos-1]*)
l=mid+1,res=mid;
else
r=mid-1;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
int i,j,pos,l,r;
cin>>o>>k>>S+1>>P+1;
ls=strlen(S+1);
lp=strlen(P+1);
init(S,hshs,ls);
init(P,hshp,lp);
pw[0]=1;
for(i=1;i<=ls;i++)
pw[i]=(pw[i-1]<<1)%p;
for(i=1;i<=ls;i++)
cnt[i]=cnt[i-1]+(S[i]=='o');
for(i=1;i<=ls-lp+1;i++){
pos=1;
for(j=1;j<=35&&pos<=lp;j++)
pos=solve(i,pos)+1;
ans=max(ans,(ll(cnt[i+lp-1]-cnt[i-1])*o+ll(lp-cnt[i+lp-1]+cnt[i-1])*k)>>j);
}
cout<<ans;
return 0;
}
详细
File "answer.code", line 4 using namespace std; ^^^^^^^^^ SyntaxError: invalid syntax