QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#865845#4882. String Strange SumGold_DinoWA 36ms21292kbC++144.5kb2025-01-22 00:43:332025-01-22 00:43:33

Judging History

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

  • [2025-01-22 00:43:33]
  • 评测
  • 测评结果:WA
  • 用时:36ms
  • 内存:21292kb
  • [2025-01-22 00:43:33]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define info(...) fprintf(stderr,__VA_ARGS__)
using ll_t=long long;
const int N=2e5+7;
int T,n;string s;
ll_t ans,sum;
int sa[N],satmp[N],*cur,*las,*head[N],cnt[N],rk[N],trk[N*2],H[N],hst[20][N];
int hook[N];vector<int>L[N];
template<class T>void clr(T*a,int n){memset(a,0,sizeof(T)*n);}
template<class T>void cpy(T*a,T*b,int n){memcpy(a,b,sizeof(T)*n);}
int qryst(int l,int r)
{
    int len=r-l+1,lg=__lg(len),w=1<<lg;
    return min(hst[lg][l],hst[lg][r-w+1]);
}
int RK(int x){return rk[n-x-1];}
int SA(int x){return n-sa[x]-1;}
int lcs(int x,int y)
{
    assert(x!=y);
    // info("%d %d ",x,y);
    x=RK(x),y=RK(y);
    // info("%d %d\n",x,y);
    if(x>y)swap(x,y);
    return qryst(x+1,y);
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(NULL);
    cin>>T;
    for(int cas=1;cas<=T;++cas)
    {
        // info("cas=%d\n",cas);
        cin>>s,n=(int)s.size(),reverse(s.begin(),s.end()),clr(cnt,128),clr(trk,n*2);
        for(int i=0;i<n;++i)++cnt[rk[i]=s[i]];
        head[0]=las=sa,cur=satmp;
        for(int i=1;i<128;++i)head[i]=head[i-1]+cnt[i-1];
        for(int i=0;i<n;++i)*(head[rk[i]]++)=i;
        for(int step=1;step<=n;step<<=1)
        {
            clr(cnt,max(n,128));
            for(int i=n-1;i>=n-step;--i)++cnt[rk[i]];
            for(int i=0;i<n;++i)if(las[i]>=step)++cnt[rk[las[i]-step]];
            head[0]=cur;
            for(int i=1;i<max(n,128);++i)head[i]=head[i-1]+cnt[i-1];
            for(int i=n-1;i>=n-step;--i)*(head[rk[i]]++)=i;
            for(int i=0;i<n;++i)if(las[i]>=step)*(head[rk[las[i]-step]]++)=las[i]-step;
            cpy(trk,rk,n);
            for(int i=0;i<n;++i)rk[cur[i]]=(i?rk[cur[i-1]]+(trk[cur[i]]!=trk[cur[i-1]]||trk[cur[i]+step]!=trk[cur[i-1]+step]):0);
            swap(las,cur);
        // for(int i=0;i<n;++i)info("%d%c",rk[i]," \n"[i==n-1]);
        }
        for(int i=0;i<n;++i)sa[i]=las[i],rk[sa[i]]=i;
        // info("%s\n",s.c_str());
        // for(int i=0;i<n;++i,info("\n"))for(int j=sa[i];j<n;++j)info("%c",s[j]);
        clr(H,n);
        for(int i=0;i<n;++i)if(rk[i])
        {
            if(i)H[rk[i]]=max(0,H[rk[i-1]]-1);
            while(max(i,sa[rk[i]-1])+H[rk[i]]<n&&s[i+H[rk[i]]]==s[sa[rk[i]-1]+H[rk[i]]])++H[rk[i]];
            hst[0][rk[i]]=H[rk[i]];
        }
        // for(int i=0;i<n;++i)info("%d\n",rk[i]);
        for(int i=1;(1<<i)<=n;++i)for(int j=0;j+(1<<i)<=n;++j)
            hst[i][j]=min(hst[i-1][j],hst[i-1][j+(1<<(i-1))]);
        reverse(s.begin(),s.end());
        int K=(int)sqrt(n);
        // info("K=%d\n",K);
        ans=sum=0;
        for(int i=0;i<n;++i)L[i].clear(),hook[i]=i;
        // info("%d %d\n",rk[2],rk[0]);
        for(int r=0;r<n;++r)
        {
            // info("[r=%d]\n",r);
            vector<pair<int,int>>prio;
            if(r>=K)
            {
                for(int x=max(0,RK(r)-K+1);x<=min(n-1,RK(r)+K-1);++x)
                {
                    if(x==RK(r))continue;
                    int t=SA(x);
                    assert(t>=0);
                    if(t>=r)continue;
                    int cs=lcs(t,r);
                    // info("t=%d lcs=%d\n",t,cs);
                    auto chk=[&](int l){return cs>=r-l+1;};
                    while(!L[t+1].empty()&&chk(L[t+1].back()))
                    {
                        int l=L[t+1].back();
                        // sum-=hook[l],hook[l]=hook[hook[l]-(r-l+1)],sum+=hook[l];
                        prio.push_back({hook[l]-(r-l+1),l});
                        L[t+1].pop_back();
                        // L[hook[l]].push_back(l);
                    }
                }
            }
            for(int l=max(0,r-K+1);l<r;++l)
                if(hook[l]&&lcs(hook[l]-1,r)>=r-l+1)
                    // sum-=hook[l],hook[l]=hook[hook[l]-(r-l+1)],sum+=hook[l];
                    prio.push_back({hook[l]-(r-l+1),l});
            sort(prio.begin(),prio.end()),reverse(prio.begin(),prio.end());
            for(auto p:prio)
            {
                sum-=hook[p.second],hook[p.second]=hook[p.first],sum+=hook[p.second];
            }
            sort(prio.begin(),prio.end(),[&](pair<int,int>a,pair<int,int>b){return a.second<b.second;});
            for(auto p:prio)L[hook[p.second]].push_back(p.second);
            if(r&&s[r]==s[r-1])hook[r]=hook[r-1];
            sum+=hook[r];
            // for(int i=0;i<=r;++i)info("%d%c",hook[i]," \n"[i==r]);
            // info("sum=%lld\n",sum);
            ans+=1ll*r*(r+1)/2-sum;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 19824kb

input:

8
aa
ab
ababa
abaaba
abacaba
abaaababaab
aababcabcbc
abcdabcabaabcd

output:

1
0
6
7
0
74
51
20

result:

ok 8 numbers

Test #2:

score: 0
Accepted
time: 36ms
memory: 19420kb

input:

100000
ff
ki
wb
vc
bb
cq
tt
gl
xb
tt
ll
it
bb
yy
dd
yg
tt
vq
gg
ua
ff
nn
aa
yq
ee
ae
sj
yy
cd
qk
vk
ts
tt
cm
rr
yk
sh
fv
vm
rr
tl
vv
bb
rl
jx
pv
tx
ib
dp
oo
lx
jo
bb
dl
sj
sn
db
kk
oo
rk
yy
gz
ff
ha
ja
ax
hn
ww
ms
yy
kf
zz
ss
ii
km
uv
mn
si
ng
hh
yq
lq
bq
ed
bb
bw
jj
pp
ss
xg
ff
gm
ee
cc
fn
vv
rc
nn...

output:

1
0
0
0
1
0
1
0
0
1
1
0
1
1
1
0
1
0
1
0
1
1
1
0
1
0
0
1
0
0
0
0
1
0
1
0
0
0
0
1
0
1
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
1
0
1
0
1
0
0
0
0
1
0
1
0
1
1
1
0
0
0
0
0
1
0
0
0
0
1
0
1
1
1
0
1
0
1
1
0
1
0
1
0
0
1
1
1
0
0
0
1
1
0
0
1
1
1
0
1
1
1
1
1
0
0
1
0
0
0
1
1
1
0
0
1
0
1
1
1
1
1
1
0
0
0
0
0
1
0
1
0
0
0
1
...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 28ms
memory: 18392kb

input:

40000
nbbnn
tttuu
rfeer
omhom
qqcmq
yyiyi
tlttt
jhjtj
ixiyx
bnnon
iwpiw
uzluz
ffqfj
dyddl
szkss
dauud
dddiy
gggtt
ebbee
uboob
nnnnv
rrjrj
cjccj
xnnyy
mwmjw
wyyyq
vvuvp
vyzyv
sssss
vvsvs
rhxxr
pkkpk
xsxss
ngncn
wzwjz
khkth
jjjjj
vvvbb
unnxn
aqlqq
mmgmg
iiiji
lyllv
luuuu
itizt
fsffs
xggii
jqqtj
mummd
...

output:

4
11
2
0
4
7
4
0
0
3
0
0
4
2
1
2
10
11
4
2
16
7
4
4
0
7
4
0
20
7
2
3
5
0
0
0
20
11
3
1
7
10
2
10
0
4
4
3
2
3
4
6
1
4
10
3
6
10
10
16
7
7
0
10
5
0
2
16
0
6
1
0
1
2
5
2
5
6
20
10
0
8
10
3
16
7
0
8
4
3
0
1
7
0
2
4
4
5
3
7
2
4
16
4
1
8
10
7
4
3
4
4
6
2
2
4
6
2
4
5
4
3
10
5
0
4
16
2
3
0
3
4
1
1
4
4
11
2
...

result:

ok 40000 numbers

Test #4:

score: -100
Wrong Answer
time: 28ms
memory: 21292kb

input:

20000
iijjijiijj
fxffxfffxx
kkiiiiiiii
oppopopppo
iiooiioooi
gggxxxxggg
oxxoxxxoox
puuuppupuu
ppssspspps
eefffeefff
xxtxxxttxt
yyppypyppp
kkwwkkwwkk
bvvvbvbbbv
attataaaat
boooobbobo
hhhhfhhhff
nnhhhnhhhh
cdccccdccd
axxxaxaxxa
qqnnnnnqnq
eeexxeeeex
ppkkkkkkkp
uusussusss
iwiwiiwiii
gglgllgggg
wwwrrrwr...

output:

40
58
93
52
40
57
56
34
44
36
52
46
41
47
41
47
77
38
56
52
65
47
86
56
61
50
51
34
58
41
52
47
60
92
61
56
64
55
65
48
56
77
80
62
55
57
41
58
44
93
63
49
54
59
50
55
111
58
52
52
39
35
63
50
111
84
140
75
78
40
99
56
49
40
68
45
77
54
47
59
52
59
50
86
72
54
36
59
33
121
84
44
28
40
57
55
46
121
6...

result:

wrong answer 5th numbers differ - expected: '52', found: '40'