QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #460753 | #6419. Baby's First Suffix Array Problem | WrongAnswer_90 | WA | 24ms | 16400kb | C++14 | 7.9kb | 2024-07-02 07:11:02 | 2024-07-02 07:11:03 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define ll long long
#define lll __int128
#define fi first
#define se second
#define e emplace
#define eb emplace_back
#define db double
#define ef emplace_front
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vp vector<pii>
#define mp make_pair
//#define LOCALJUDGE
#define int ll
bool ST;
static const ll MOD=998244353,Phi=998244352,inv2=499122177,Root=3,iRoot=332748118;
static const ll inf=1073741823,INF=4557430888798830399;
static const double eps=1e-8,pi=3.1415926535;
char in[1<<20],*p1=in,*p2=in;
using namespace std;
//#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
struct tup{int x,y,z;tup(int X=0,int Y=0,int Z=0){x=X,y=Y,z=Z;}};
namespace FastIO
{
template<typename T> inline void write(T x,char ch=' ')
{
if(is_same<char,T>::value)putchar(x);
else
{
if(x<0)x=-x,putchar('-');
static char st[25];int top=0;
do{st[top++]=x%10+'0',x/=10;}while(x);
while(top)putchar(st[--top]);
}
ch!='~'?putchar(ch):0;
}
inline void write(const char*x,char ch=' ')
{
for(int i=0;x[i]!='\0';++i)putchar(x[i]);
ch!='~'?putchar(ch):0;
}
inline void read(char&s){do s=getchar();while(s=='\n'||s==' ');}
inline void read(char s[])
{
int len=0;char st;
do st=getchar();while(st=='\n'||st==' ');
s[++len]=st,st=getchar();
while(st!='\n'&&st!=' ')s[++len]=st,st=getchar();
s[++len]='\0';
}
template<typename T> inline void read(T &s)
{
s=0;char ch=getchar();
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
bool tf=(ch=='-')&&(ch=getchar());
while((ch>='0')&&(ch<='9'))s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
s=(tf?-s:s);
}
template<typename T1,typename T2> inline void read(pair<T1,T2> &s){read(s.fi),read(s.se);}
template<typename T,typename...Args> inline void write(T x,Args...args){write(x,'~'),write(args...);}
template<typename T,typename...Args> inline void read(T&x,Args&...args){read(x),read(args...);}
}
using namespace FastIO;
namespace MTool
{
inline int Cadd(int a,int b){return (ll)a+b>=MOD?(ll)a+b-MOD:a+b;}
inline int Cdel(int a,int b){return a-b<0?a-b+MOD:a-b;}
inline int Cmul(int a,int b){return 1ll*a*b%MOD;}
inline int sqr(int a){return 1ll*a*a%MOD;}
inline void Madd(int&a,int b){a=((ll)a+b>=MOD?(ll)a+b-MOD:a+b);}
inline void Mdel(int&a,int b){a=(a-b<0?a-b+MOD:a-b);}
inline void Mmul(int&a,int b){a=1ll*a*b%MOD;}
template<typename T> inline bool Mmax(T&a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool Mmin(T&a,T b){return a>b?a=b,1:0;}
template<typename...Args> inline void Madd(int&a,int b,Args...args){Madd(a,b),Madd(a,args...);}
template<typename...Args> inline void Mmul(int&a,int b,Args...args){Mmul(a,b),Mmul(a,args...);}
template<typename...Args> inline void Mdel(int&a,int b,Args...args){Mdel(a,b),Mdel(a,args...);}
template<typename...Args> inline int Cadd(int a,int b,Args...args){return Cadd(Cadd(a,b),args...);}
template<typename...Args> inline int Cmul(int a,int b,Args...args){return Cmul(Cmul(a,b),args...);}
template<typename...Args> inline int Cdel(int a,int b,Args...args){return Cdel(Cdel(a,b),args...);}
template<typename...Args,typename T> inline bool Mmax(T&a,T b,Args...args){return Mmax(a,b)|Mmax(a,args...);}
template<typename...Args,typename T> inline bool Mmin(T&a,T b,Args...args){return Mmin(a,b)|Mmin(a,args...);}
inline int power(int x,int y){int s=1;for(;y;y>>=1,Mmul(x,x))if(y&1)Mmul(s,x);return s;}
}
using namespace MTool;
namespace WrongAnswer_90
{
int T,m,n,q,ans[50010],b[50010],val[50010];
int x[100010],y[100010],F[18][50010],rk[50010],sa[50010];
char s[50010];
vector<tup> ve[50010],Ve[50010];
inline int LCP(int x,int y)
{
if(x>n||y>n)return 0;
if(x==y)return n-x+1;
if((x=rk[x])>(y=rk[y]))swap(x,y);
int k=__lg(y-x++);
return min(F[k][x],F[k][y-(1<<k)+1]);
}
bool cmp(pii a,pii b){return a.fi<b.fi;}
namespace BIT
{
int t[50010];
inline void add(int x,int y=1){for(;x<=n;x+=x&-x)t[x]+=y;}
inline int ask(int x){int s=0;for(;x;x-=x&-x)s+=t[x];return s;}
inline int ask(int l,int r){if(l>r)return 0;return ask(r)-ask(l-1);}
}
using namespace BIT;
struct Node{int l,r,up,id;};
vector<Node> hlp;
inline bool cmp1(Node x,Node y){return x.up<y.up||(x.up==y.up&&x.id<y.id);}
void solve(int l,int r)
{
if(l==r)return;
int mid=l+((r-l)>>1);
val[mid]=inf;
for(int i=mid-1;i>=1;--i)val[i]=min(val[i+1],F[0][i+1]);
for(int i=mid+1;i<=r;++i)val[i]=min(val[i-1],F[0][i]);
for(int j=mid+1,i=mid;j<=r;++j)
{
while(i>=l&&val[j]<=val[i])
{
for(auto p:Ve[i])
ans[p.z]+=ask(max(p.x+1,p.y-val[i]+1),p.y);
--i;
}
add(sa[j]);
}
for(int i=mid+1;i<=r;++i)add(sa[i],-1);
hlp.clear();
for(int i=l;i<=mid;++i)
{
for(auto p:Ve[i])
{
int up=val[i],l=p.x+1,r=p.y,lim=p.y+1;
if(r+up<lim)continue;
if(l+up<r)l=r-up;
hlp.eb((Node){l,r,up,p.z});
}
}
for(int i=mid+1;i<=r;++i)hlp.eb((Node){sa[i],sa[i],val[i],0});
sort(hlp.begin(),hlp.end(),cmp1);
for(auto p:hlp)
{
if(!p.id)add(p.l);
else ans[p.id]+=ask(p.r)-ask(p.l-1);
}
for(auto p:hlp)if(!p.id)add(p.l,-1);
hlp.clear();
for(int i=l;i<=mid;++i)
{
for(auto p:Ve[i])
{
int up=val[i],l=p.x+1,r=p.y,lim=p.y+1;
if(r+up<lim)continue;
if(l+up<r)l=r-up;
hlp.eb((Node){l,r,lim,p.z});
}
}
for(int i=mid+1;i<=r;++i)hlp.eb((Node){sa[i],sa[i],sa[i]+val[i]+1,0});
sort(hlp.begin(),hlp.end(),cmp1);
for(auto p:hlp)
{
if(!p.id)add(p.l);
else ans[p.id]-=ask(p.r)-ask(p.l-1);
}
for(auto p:hlp)if(!p.id)add(p.l,-1);
solve(l,mid),solve(mid+1,r);
}
tup a[50010];
inline void mian()
{
read(T);
while(T--)
{
read(n,q),m=128,read(s),s[n+1]='*';
for(int i=1;i<=m;++i)b[i]=0;
for(int i=1;i<=n;++i)++b[x[i]=s[i]],Ve[i].clear();
for(int i=2;i<=m;++i)b[i]+=b[i-1];
for(int i=1;i<=n;++i)sa[b[x[i]]--]=i;
for(int k=1,num=0;k<=n;k<<=1,num=0)
{
for(int i=n;i>n-k;--i)y[++num]=i;
for(int i=1;i<=n;++i)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=1;i<=m;++i)b[i]=0;
for(int i=1;i<=n;++i)++b[x[i]];
for(int i=2;i<=m;++i)b[i]+=b[i-1];
for(int i=n;i>=1;--i)sa[b[x[y[i]]]--]=y[i];
for(int i=1;i<=n;++i)swap(x[i],y[i]);
x[sa[1]]=1;
for(int i=2;i<=n;++i)
{
if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=x[sa[i-1]];
else x[sa[i]]=x[sa[i-1]]+1;
}
if((m=x[sa[n]])==n)break;
}
for(int i=1;i<=n;++i)rk[sa[i]]=i;
for(int i=1,k=0;i<=n;++i,k?--k:0)
{
while(s[i+k]==s[sa[rk[i]-1]+k])++k;
F[0][rk[i]]=k;
}
for(int i=1;i<18;++i)
{
for(int j=1;j+(1<<i)-1<=n;++j)
F[i][j]=min(F[i-1][j],F[i-1][j+(1<<(i-1))]);
}
// for(int i=1;i<=n;++i)write(rk[i]);puts("");
for(int i=1;i<=q;++i)
{
ans[i]=0,read(a[i].x,a[i].y,a[i].z);
ve[rk[a[i].z]-1].eb(tup(a[i].x,a[i].y,i));
Ve[rk[a[i].z]].eb(tup(a[i].z,a[i].y,i));
int L=1,R=rk[a[i].z],mid;
while(L<R)
{
mid=L+((R-L)>>1);
if(LCP(sa[mid],a[i].z)>=a[i].y-a[i].z+1)R=mid;
else L=mid+1;
}
ve[L-1].eb(tup(a[i].x,a[i].z-1,i));
ve[rk[a[i].z]-1].eb(tup(a[i].x,a[i].z-1,-i));
}
for(int i=1;i<=n;++i)
{
add(sa[i]);
for(auto p:ve[i])
{
if(p.z>0)Madd(ans[p.z],ask(p.y)-ask(p.x-1));
else Madd(ans[-p.z],ask(p.x-1)-ask(p.y));
}
}
for(int i=1;i<=n;++i)t[i]=0,ve[i].clear();
solve(1,n);
for(int i=1;i<=q;++i)write(ans[i]+1,'\n');
}
}
}
bool ED;
signed main()
{
#ifdef LOCALJUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
double st=clock();
WrongAnswer_90::mian();
double ed=clock();
#ifndef LOCALJUDGE
cerr<<endl;
#endif
cerr<<"Time: "<<ed-st<<" ms\n";
#ifdef LOCALJUDGE
cerr<<" ";
#endif
cerr<<"Memory: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 16156kb
input:
2 10 4 baaabbabba 2 8 3 1 1 1 2 3 2 2 5 4 20 3 cccbccbadaacbbbcccab 14 17 16 3 20 17 17 20 18
output:
2 1 2 3 4 15 3
result:
ok 7 numbers
Test #2:
score: -100
Wrong Answer
time: 24ms
memory: 16400kb
input:
8994 10 10 abaabbaabb 2 8 3 1 8 5 6 9 6 9 9 9 5 10 7 5 7 7 7 8 7 5 6 6 1 9 9 3 9 5 2 1 ab 1 2 1 8 6 bbabaabb 3 7 7 5 7 7 1 5 1 1 4 3 3 5 3 5 5 5 10 3 aababbaaab 3 4 4 6 9 8 4 6 6 7 3 babbaab 5 6 5 3 6 6 1 6 6 9 3 baaaabbba 2 5 2 8 9 8 1 4 4 9 2 babaababa 2 4 4 2 6 3 2 3 ba 1 2 2 1 2 1 2 2 2 10 2 aba...
output:
2 8 4 1 1 1 1 1 6 7 1 4 3 5 1 2 1 1 2 2 2 1 1 4 2 1 1 5 1 2 1 5 2 3 1 1 1 4 3 2 1 1 3 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 3 2 1 2 1 1 2 3 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 2 2 1 2 2 1 2 1 2 1 1 1 5 1 1 3 2 4 1 2 1 2 1 1 1 4 2 2 2 6 1 1 2 2 1 2 1 4 4 1 1 1 1 1 1 1 2 1 4 2 3 2 2 1 4 2 2 2 2 1 2 ...
result:
wrong answer 1st numbers differ - expected: '3', found: '2'