QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719913#9406. Trianglebyron10000WA 4ms46036kbC++145.0kb2024-11-07 09:48:222024-11-07 09:48:23

Judging History

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

  • [2024-11-07 09:48:23]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:46036kb
  • [2024-11-07 09:48:22]
  • 提交

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<<" ";
    }
    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: 0ms
memory: 39672kb

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: 4ms
memory: 46036kb

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 cyt cyt rfhgomg cyt cyt k cy...jcnzuxq ncitwxsdpp sojcnzuxq o '