QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719893#9406. Trianglebyron10000WA 3ms47820kbC++144.9kb2024-11-07 09:39:542024-11-07 09:39:55

Judging History

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

  • [2024-11-07 09:39:55]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:47820kb
  • [2024-11-07 09:39:54]
  • 提交

answer

#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define _UN using namespace
using namespace std;
const int MAXN=3e5+10;
struct SA{
    char S[MAXN]; int n;
    int sa[MAXN],sa1[MAXN],rk[MAXN*2],lrk[MAXN*2],cnt[MAXN],H[MAXN],st[20][MAXN];
    void main(){
        iota(sa+1,sa+n+1,1);
        copy_n(S+1,n,rk+1);
        int mxrk=*max_element(rk+1,rk+n+1);
        fill_n(cnt+1,mxrk,0);
        RNG(i,1,n) cnt[rk[i]]++;
        RNG(i,1,mxrk) cnt[i]+=cnt[i-1];
        RNG(i,1,n) sa[cnt[rk[i]]--]=i;
        for(int len=1; ; len*=2){
            iota(sa1+1,sa1+len+1,n-len+1);
            int c=len;
            RNG(i,1,n){
                if(sa[i]>len) sa1[++c]=sa[i]-len;
            }
            assert(c==n);
            fill_n(cnt+1,mxrk,0);
            RNG(i,1,n) cnt[rk[i]]++;
            RNG(i,1,mxrk) cnt[i]+=cnt[i-1];
            IRNG(i,n,1) sa[cnt[rk[sa1[i]]]--]=sa1[i];
            copy_n(rk+1,n,lrk);
            mxrk=0;
            RNG(i,1,n){
                if(!(lrk[sa[i]]==lrk[sa[i-1]]&&lrk[sa[i]+len]==lrk[sa[i-1]+len])) mxrk++;
                rk[sa[i]]=mxrk;
            }
            if(mxrk==n) break;
        }
        RNG(i,1,n,c=0){
            if(c) c--;
            if(rk[i]==1) continue;
            while(S[i+c]==S[sa[rk[i]-1]+c]) c++;
            H[rk[i]]=c;
        }
        copy_n(H+1,n,st[0]+1);
        RNG(t,1,__lg(n-1)){
            RNG(i,2,n-(1<<t)+1) st[t][i]=min(st[t-1][i],st[t-1][i+(1<<(t-1))]);
        }
    }
    int lcp(int i,int j){
        if(i==j) return n-i+1;
        i=rk[i],j=rk[j];
        if(i>j) swap(i,j);
        int t=__lg(j-i);
        return min(st[t][i+1],st[t][j-(1<<t)+1]);
    }
} sa;
int n;
struct BIT{
    int A[MAXN];
    void reset(){ fill_n(A+1,n,0); }
    void upd(int i,int x){
        for(; i<=n; i+=i&-i) A[i]+=x;
    }
    int qry(int i){
        int ret=0;
        for(; i; i-=i&-i) ret+=A[i];
        return ret;
    }
} bit;
int pos[MAXN]; long ans;
struct{ string s; int c,len; } A[MAXN];
int ord[MAXN],iord[MAXN];
struct Qt{ int i; long x; }; vector<Qt> qry[MAXN];
int lcp(int i,int ip,int j,int jp){ return min({sa.lcp(pos[i]+ip,pos[j]+jp),A[i].len-ip,A[j].len-jp}); }
bool is_pre(int i,int j){ return !strncmp(A[i].s.data(),A[j].s.data(),min(A[i].len,A[j].len)); }
int cmp(int i,int j){
    int p=lcp(j,0,j,A[i].len);
    if(A[i].len+p<A[j].len) return A[j].s[p]-A[j].s[p+A[i].len];
    p=lcp(j,0,j,A[j].len-A[i].len);
    if(p==A[i].len) return 0;
    return A[j].s[A[j].len-A[i].len+p]-A[i].s[p];
}
void case_main(){
    cin>>n;
    RNG(i,1,n) cin>>A[i].s;
    sort(A+1,A+n+1,[](const auto& x,const auto& y){ return x.s<y.s; });
    {
        int n1=0;
        RNG(i,1,n){
            if(A[i].s==A[i-1].s) A[n1].c++;
            else A[++n1]={A[i].s,1,int(A[i].s.size())};
        }
        n=n1;
    }
    sa.n=0;
    RNG(i,1,n) pos[i]=sa.n+1,copy_n(A[i].s.data(),A[i].len,sa.S+sa.n+1),sa.n+=int(A[i].s.size());
    sa.main();
    iota(ord+1,ord+n+1,1);
    sort(ord+1,ord+n+1,[](int i,int j){
        if(!is_pre(i,j)) return i<j;
        else if(i<j) return cmp(i,j)<0;
        else return cmp(j,i)>0;
    });
    RNG(i,1,n) iord[ord[i]]=i;
    ans=0;
    RNG(i,1,n) qry[i].clear();
    vector<int> stk;
    RNG(i,1,n){
        while(stk.size()&&!is_pre(stk.back(),i)) stk.pop_back();
        for(int j:stk){
            int l=1,r=i-1,res=i;
            while(l<=r){
                auto mid=(l+r)/2;
                int p=lcp(mid,0,i,A[j].len);
                bool flag;
                if(p==A[mid].len) flag=0;
                else if(p+A[j].len==A[i].len) flag=1;
                else flag=A[mid].s[p]>A[i].s[A[j].len+p];
                if(flag) res=mid,r=mid-1;
                else l=mid+1;
            }
            if(res<i) qry[res-1].push_back({iord[j]-1,-1l*A[i].c*A[j].c}),qry[i-1].push_back({iord[j]-1,1l*A[i].c*A[j].c});
            if(res<=j) ans+=1l*A[i].c*A[j].c*(A[j].c-1)/2;
        }
        stk.push_back(i);
    }
    RNG(i,1,n,c=0){
        ans+=1l*A[i].c*(A[i].c-1)*(A[i].c-2)/6+1l*A[i].c*(A[i].c-1)/2*c;
        c+=A[i].c;
    }
    bit.reset();
    RNG(i,1,n){
        bit.upd(iord[i],A[i].c);
        for(auto [j,x]:qry[i]) ans+=x*bit.qry(j);
    }
    cout<<ans<<"\n";
}
int _curcas;
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
//  freopen("out","w",stdout);
//  freopen("/dev/null","w",stderr);
#else
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int cas; cin>>cas;
    RNG(_,1,cas) _curcas=_,case_main();
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 41656kb

input:

3
6
cbaa
cb
cb
cbaa
ba
ba
3
sdcpc
sd
cpc
1
ccpc

output:

16
0
0

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 47820kb

input:

14
1
lfpbavjsm
2
pdtlkfwn
mbd
3
dvqksg
dvqksg
uhbhpyhj
4
ombwb
ombwb
ombwb
ombwb
5
oztclz
oztclz
oztclz
oztclz
kul
6
vco
vco
vco
dtktsqtinm
vco
vco
7
tb
tb
kowbsu
ygkfphcij
tb
uvei
tb
8
vxxtxssht
abnsxbf
bydaae
bydaae
udalyvmcef
bydaae
bydaae
bydaae
9
aaze
zvyonw
qjfv
mmhkef
qjfv
qjfv
qjfv
mmhkef
qj...

output:

0
0
0
4
10
20
10
20
41
14
63
74
18
11082

result:

wrong answer 14th lines differ - expected: '11081', found: '11082'