QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#413641#7901. Basic Substring Structuregrass8cow#WA 17ms32532kbC++172.5kb2024-05-17 20:22:562024-05-17 20:22:56

Judging History

你现在查看的是最新测评结果

  • [2024-05-17 20:22:56]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:32532kb
  • [2024-05-17 20:22:56]
  • 提交

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'