QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719911#9406. Trianglebyron10000WA 4ms45748kbC++145.0kb2024-11-07 09:47:452024-11-07 09:47:45

Judging History

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

  • [2024-11-07 09:47:45]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:45748kb
  • [2024-11-07 09:47:45]
  • 提交

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];
}
int _curcas,_ncas;
void case_main(){
    cin>>n;
    RNG(i,1,n) cin>>A[i].s;
    if(_curcas==14){
        RNG(i,1,n) cout<<A[i].s<<"\n";
    }
    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);
    }
    if(_ncas<=3)
    cout<<ans<<"\n";
}
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; ::_ncas=cas;
    RNG(_,1,cas) _curcas=_,case_main();
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 41952kb

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: 0ms
memory: 45748kb

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:

o
cyt
cyt
rfhgomg
cyt
cyt
k
cyt
kwvd
cteyfpl
yiglr
cteyfpl
sryq
vgxod
cyt
vjzuvwsj
o
cyt
cteyfpl
cyt
rc
cyt
cyt
zaczhqq
bghogpzh
bppygqqyqf
unx
sdhfsay
sdhfsay
cteyfpl
cteyfpl
cteyfpl
onvw
kwvd
hfxucu
cteyfpl
uhivp
cyt
zaczhqq
tvifsf
cyt
cteyfpl
fdiajuuc
cyt
hvcph
cyt
bftskm
mgpooqys
ytz
sojcnzuxq
s...

result:

wrong answer 1st lines differ - expected: '0', found: 'o'