QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#413641 | #7901. Basic Substring Structure | grass8cow# | WA | 17ms | 32532kb | C++17 | 2.5kb | 2024-05-17 20:22:56 | 2024-05-17 20:22:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int lg[1010000];
int c[1001000],rk[1001000],t[1001000],tr[1001000],sa[1001000],n,h[1000100],f[1010000][20];
int lcp(int x,int y){
if(x>n||y>n)return 0;
x=rk[x],y=rk[y];if(x>y)swap(x,y);x++;
int k=lg[y-x+1];
return min(f[x][k],f[y-(1<<k)+1][k]);
}
void SA(){
int m=n;
for(int i=1;i<=n*4;i++)tr[i]=0;
for(int i=1;i<=m;i++)t[i]=0;
for(int i=1;i<=n;i++)t[rk[i]=c[i]]++;
for(int i=1;i<=m;i++)t[i]+=t[i-1];
for(int i=n;i;i--)sa[t[rk[i]]--]=i;
for(int k=1;;k<<=1){
int p=0;
for(int i=n-k+1;i<=n;i++)tr[++p]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)tr[++p]=sa[i]-k;
for(int i=1;i<=m;i++)t[i]=0;
for(int i=1;i<=n;i++)t[rk[i]]++;
for(int i=1;i<=m;i++)t[i]+=t[i-1];
for(int i=n;i;i--)sa[t[rk[tr[i]]]--]=tr[i];
rk[sa[1]]=p=1;
for(int i=1;i<=n;i++)tr[i]=rk[i];
for(int i=2;i<=n;i++)
rk[sa[i]]=((tr[sa[i-1]]==tr[sa[i]]&&tr[sa[i-1]+k]==tr[sa[i]+k])?p:(++p));
m=p;if(m==n)break;
}
for(int i=1,k=0;i<=n;i++){
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<=n&&j+k<=n&&c[i+k]==c[j+k])k++;
f[rk[i]][0]=k;
}
for(int j=1;j<20;j++)for(int i=1;i+(1<<j)-1<=n;i++)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int sv(int x,int y,char cy){
int lc=1+min(lcp(x+1,y+1),y-x-1);
if(lc<y-x||y*2-x>n||cy!=c[y*2-x])return lc;
return lc+1+lcp(y+1,1+y+y-x);
}
#define long long
ll c1[200100],c2[200100];
void co(int l,int r){
c1[l]-=l,c1[r+1]+=l,c2[l]++,c2[r+1]--;
}
map<int,ll>gt[201000];
void sol(){
scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&c[i]),c1[i]=c2[i]=0,gt[i].clear();SA();
for(int i=2;i<=n;i++){
int l=lcp(1,i);
if(l+1<i){
c1[l+1]+=l,c1[i]-=l,c1[i+l]+=l;
co(1,l),co(i,i+l-1);
if(i+l>n)continue;
gt[i+l][c[l+1]]+=sv(l+1,i+l,c[l+1]),gt[l+1][c[i+l]]+=sv(l+1,i+l,c[i+l]);
}
else{
co(1,i-1),co(i,i+l-1),c1[i+l]+=l;
if(i+l>n)continue;
gt[i+l][c[l+1]]+=sv(l+1,i+l,c[l+1]);
}
}
ll ans=0;
for(int i=1;i<=n;i++){
c1[i]+=c1[i-1],c2[i]+=c2[i-1];
ll ve=c1[i]+c2[i]*i+n,mx=0;
for(auto it:gt[i])mx=max(mx,it.second);
ve+=mx;
ans+=(ve^i);
}
printf("%lld\n",ans);
}
int main(){
lg[0]=-1;
for(int i=1;i<=1000000;i++)lg[i]=lg[i>>1]+1;
int T;scanf("%d",&T);while(T--)sol();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 32532kb
input:
2 4 2 1 1 2 12 1 1 4 5 1 4 1 9 1 9 8 10
output:
15 217
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 17ms
memory: 32516kb
input:
10000 8 2 1 2 1 1 1 2 2 9 2 2 1 2 1 2 1 2 1 15 2 1 2 1 1 1 1 2 2 1 2 1 2 2 1 2 1 1 10 2 1 1 1 2 2 1 1 2 2 3 2 1 2 11 1 2 2 1 1 2 1 2 2 1 1 14 2 1 1 1 1 2 1 1 1 2 2 1 2 1 12 2 2 2 1 2 2 2 1 1 2 1 2 4 2 1 1 2 8 1 2 2 2 1 2 1 1 8 1 1 2 1 2 1 1 1 6 2 1 1 1 2 2 14 2 2 1 1 1 1 2 2 2 1 2 2 1 1 10 1 2 2 1 1...
output:
94 128 347 3 211 9 265 363 278 15 95 114 58 348 225 3 335 364 377 316 3 19 122 66 15 83 36 258 11 63 28 90 85 103 252 191 21 48 303 63 102 20 24 68 316 362 266 309 355 281 326 281 231 312 3 330 54 328 3 69 32 147 322 39 338 90 242 3 165 346 245 20 155 3 404 393 392 81 269 360 20 54 21 279 3 17 351 3...
result:
wrong answer 514th lines differ - expected: '17', found: '16'