QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #404699 | #6419. Baby's First Suffix Array Problem | zjy0001 | Compile Error | / | / | C++17 | 3.3kb | 2024-05-04 14:54:30 | 2024-05-04 14:54:31 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long
using namespace std;
const int N=5e4+5;
int n,q;char s[N];
tuple<int,int,int>A[N*2];
vector<tuple<int,int,int>>Q[N],nQ[N];
int sa[N],rk[N],height[N],ans[N],T[N*4];
struct FenwickTree{
int n,c[N];
inline void build(const int&_n){n=_n,fill(c+1,c+n+1,0);}
inline void add(int x,const int&y){for(;x<=n;x+=x&-x)c[x]+=y;}
inline int sum(int x,int z=0){for(;x;x-=x&-x)z+=c[x];return z;}
}T0;
inline void SA(char *s,int n){
static int t1[N],t2[N],cnt[N];
int *x=t1,*y=t2,m=127;
for(int i=1;i<=n;++i)++cnt[x[i]=s[i]];
for(int i=2;i<=m;++i)cnt[i]+=cnt[i-1];
for(int i=n;i>=1;--i)sa[cnt[x[i]]--]=i;
fill(cnt+1,cnt+m+1,0);
for(int k=1;;k<<=1){
int p=0;
for(int i=n-k+1;i<=n;++i)y[++p]=i;
for(int i=1;i<=n;++i)if(sa[i]>k)y[++p]=sa[i]-k;
for(int i=1;i<=n;++i)++cnt[x[i]];
for(int i=2;i<=m;++i)cnt[i]+=cnt[i-1];
for(int i=n;i>=1;--i)sa[cnt[x[y[i]]]--]=y[i],y[i]=0;
fill(cnt+1,cnt+m+1,0);
swap(x,y),x[sa[p=1]]=1;
for(int i=2;i<=n;++i)
x[sa[i]]=p=p+1-(y[sa[i]]==y[sa[i-1]]&&(max(sa[i],s[i-1])+k>n||y[sa[i]+k]==y[sa[i-1]+k]);
if((m=p)>=n)break;
}
for(int i=1;i<=n;++i)rk[sa[i]]=i;
for(int i=1,j=0;i<=n;++i){
j=max(j-1,0);
if(rk[i]==1)continue;
int k=sa[rk[i]-1];
while(i+j<=n&&j+k<=n&&s[i+j]==s[j+k])++j;
height[rk[i]]=j;
}
}
inline void build(int p,int l,int r){
if(l==r)return T[p]=height[l],void();
const int mid=(l+r)>>1,ls=p*2,rs=p*2+1;
build(ls,l,mid),build(rs,mid+1,r);
T[p]=min(T[ls],T[rs]);
}
inline int qry(int p,int l,int r,int x,int y){
if(T[p]>y)return l-1;
if(l==r)return l;
const int mid=(l+r)>>1,ls=p*2,rs=p*2+1;
const int z=(x>mid?qry(rs,mid+1,r,x,y):mid);
return z<=mid?qry(ls,l,mid,x,y):z;
}
inline void solve(int l,int r){
if(l>=r){
nQ[l].clear();
return;
}
const int p=(l+r)>>1;
int m=0;
for(int i=p+1,c=height[i];i<=r;++i)
c=min(height[i],c),T0.add(sa[i],1),
A[++m]=make_tuple(sa[i]+c,0,sa[i]);
for(int i=p,c=height[i+1];i>=l;--i){
c=min(c,height[i+1]);
for(auto [k,r,id]:nQ[i])
ans[id]+=T0.sum(r)-T0.sum(max(r-c,k)),
A[++m]=make_tuple(r,id,max(r-c,k)+1);
}
for(int i=p+1;i<=r;++i)T0.add(sa[i],-1);
sort(A+1,A+m+1);
for(int i=1;i<=m;++i)
if(get<1>(A[i]))ans[get<1>(A[i])]-=T0.sum(n-get<2>(A[i])+1);
else T0.add(n-get<2>(A[i])+1,1);
for(int i=1;i<=m;++i)if(!get<1>(A[i]))T0.add(n-get<2>(A[i])+1,-1);
solve(l,p),solve(p+1,r);
}
int qc=0;
inline void MAIN(){
cin>>n>>q>>(s+1);
SA(s,n),build(1,1,n);
for(int i=1;i<=q;++i){
int l,r,k;cin>>l>>r>>k,ans[i]=1;
if(k<r)
Q[rk[k]].emplace_back(k+1,r,i),
nQ[rk[k]].emplace_back(k,r,i);
if(l<k)Q[qry(1,1,n,rk[k],r-k)-1].emplace_back(l,k-1,i);
}
T0.build(n);
for(int i=1;i<=n;++i){
T0.add(sa[i],1);
for(auto [l,r,id]:Q[i])ans[id]+=T0.sum(r)-T0.sum(l-1);
Q[i].clear();
}
T0.build(n),solve(1,n);
for(int i=1;i<=q;++i)cout<<ans[i]<<'\n';
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int t=1;cin>>t;while(t--)MAIN();
return 0;
}
/*
*/
Details
answer.code: In function ‘void SA(char*, int)’:
answer.code:36:67: error: no matching function for call to ‘max(int&, char&)’
36 | x[sa[i]]=p=p+1-(y[sa[i]]==y[sa[i-1]]&&(max(sa[i],s[i-1])+k>n||y[sa[i]+k]==y[sa[i-1]+k]);
| ~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from answer.code:1:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
257 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: template argument deduction/substitution failed:
answer.code:36:67: note: deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘char’)
36 | x[sa[i]]=p=p+1-(y[sa[i]]==y[sa[i-1]]&&(max(sa[i],s[i-1])+k>n||y[sa[i]+k]==y[sa[i-1]+k]);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
303 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: template argument deduction/substitution failed:
answer.code:36:67: note: deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘char’)
36 | x[sa[i]]=p=p+1-(y[sa[i]]==y[sa[i-1]]&&(max(sa[i],s[i-1])+k>n||y[sa[i]+k]==y[sa[i-1]+k]);
| ~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)’
5795 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: template argument deduction/substitution failed:
answer.code:36:67: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
36 | x[sa[i]]=p=p+1-(y[sa[i]]==y[sa[i-1]]&&(max(sa[i],s[i-1])+k>n||y[sa[i]+k]==y[sa[i-1]+k]);
| ~~~^~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)’
5805 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: template argument deduction/substitution failed:
answer.code:36:67: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
36 | x[sa[i]]=p=p+1-(y[sa[i]]==y[sa[i-1]]&&(max(sa[i],s[i-1])+k>n||y[sa[i]+k]==y[sa[i-1]+k]);
| ~~~^~~~~~~~~~~~~~
answer.code:36:112: error: expected ‘)’ before ‘;’ token
36 | x[sa[i]]=p=p+1-(y[sa[i]]==y[sa[i-1]]&&(max(sa[i],s[i-1])+k>n||y[sa[i]+k]==y[sa[i-1]+k]);
| ~ ^
| )