QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#722250 | #9406. Triangle | caibyte | WA | 788ms | 139004kb | C++14 | 3.2kb | 2024-11-07 18:19:18 | 2024-11-07 18:19:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F(i,l,r) for(int i=l;i r;++i)
#define R(i,r,l) for(int i=r;i l;--i)
#define pb push_back
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
template<class T=int>inline T read(){
T x=0;bool b=0;char c=getchar();
while(!isdigit(c)) b|=c=='-',c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
return b?-x:x;
}
inline char readc(){
char c=getchar();
while(isspace(c)) c=getchar();
return c;
}
namespace{
//
const int N=3e6+3;
int cn,n,sa[N],rk[N],h[N],p[N],rev[N];
char a[N];
string s[N];
inline void ins(int x){
n+=4;
F(i,0,<4){
a[n-i]=x%26+'A';
x/=26;
}
}
int x[N],y[N],c[N];
void SA(){
int m=127;
F(i,0,<=m) c[i]=0;
F(i,1,<=n) ++c[x[i]=a[i]];
F(i,1,<=m) c[i]+=c[i-1];
R(i,n,>=1) sa[c[x[i]]--]=i;
for(int k=1;k<n;k<<=1){
int cnt=0;
F(i,n-k+1,<=n) y[++cnt]=i;
F(i,1,<=n) if(sa[i]>k) y[++cnt]=sa[i]-k;
F(i,0,<=m) c[i]=0;
F(i,1,<=n) ++c[x[i]];
F(i,1,<=m) c[i]+=c[i-1];
R(i,n,>=1) sa[c[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);
x[sa[1]]=m=1;
F(i,2,<=n){
if(y[sa[i-1]]!=y[sa[i]]||y[sa[i-1]+k]!=y[sa[i]+k]) ++m;
x[sa[i]]=m;
}
if(m==n) break;
}
F(i,1,<=n) rk[sa[i]]=i;
int p=0;
F(i,1,<=n){
if(rk[i]==1) continue;
if(p) --p;
while(a[i+p]==a[sa[rk[i]-1]+p]) ++p;
h[rk[i]]=p;
}
}
struct bit{
ll c[N];
void init(){
F(i,0,<=n) c[i]=0;
}
void write(int x,ll k){
for(;x;x&=x-1) c[x]+=k;
}
ll query(int x){
ll res=0;
for(;x<=n;x+=x&-x) res+=c[x];
return res;
}
} T;
typedef pair<int,int> pii;
int st[N],siz;
ll cnt[N];
priority_queue<pii,vector<pii>,greater<pii>> q;
inline void reset(){
F(i,1,<=(n<<1)){
sa[i]=rk[i]=h[i]=p[i]=rev[i]=a[i]=0;
}
T.init();
F(i,1,<=siz) st[i]=cnt[i]=0;
n=siz=0;
}
bool cmp(const string&x,const string&y){
return x.size()<y.size();
};
ll ss;
inline void solve(){
if(clock()*1.0/CLOCKS_PER_SEC>=0.8){
cout<<ss<<"!!!\n";
exit(0);
}
cin>>cn;
F(i,1,<=cn) cin>>s[i];
sort(s+1,s+cn+1,cmp);
F(i,1,<=cn){
p[i]=n+1;rev[n+1]=i;
for(char c:s[i]){
a[++n]=c;
}
ins(i);
}
// cerr<<a+1<<'\n';
SA();
ss+=n;
ll ans=0;
F(i,2,<=n){// C
while(siz&&s[st[siz]].size()>h[i]) --siz;
if(!rev[sa[i]]) continue;
ss-=siz;
F(j,1,<=siz){// A
while(!q.empty()&&q.top().first<rk[p[st[j]]]){
int x=q.top().second;q.pop();
T.write(rk[p[st[x]]],-cnt[x]);
}
int x=rk[sa[i]+s[st[j]].size()];
ans+=T.query(x)*cnt[j];
if(x<rk[p[st[j]]]) ans-=cnt[j]*(cnt[j]+1)/2,T.write(rk[p[st[j]]],-cnt[j]);
else if(x<i) q.push({x,j});
}
while(!q.empty()){
int x=q.top().second;q.pop();
T.write(rk[p[st[x]]],-cnt[x]);
}
F(j,1,<=siz){
int x=rk[sa[i]+s[st[j]].size()];
if(x<i) T.write(rk[p[st[j]]],cnt[j]);
}
if(siz&&s[st[siz]].size()==s[rev[sa[i]]].size()) ++cnt[siz];
else ++siz,cnt[siz]=1,st[siz]=rev[sa[i]];
T.write(i,1);
}
assert(ss>=0);
cout<<ans<<'\n';
reset();
}
void work(){
ios::sync_with_stdio(0);
int T;
cin>>T;
while(T--) solve();
}
}
#if 0
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#else
#define file(x)
#endif
signed main(){file("");work();return 0;}
詳細信息
Test #1:
score: 100
Accepted
time: 23ms
memory: 136952kb
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: 0
Accepted
time: 115ms
memory: 137016kb
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 11081
result:
ok 14 lines
Test #3:
score: 0
Accepted
time: 104ms
memory: 136780kb
input:
11 10 bppzfsncq bppzfsncq vcqxgcehdx bppzfsncq bppzfsncq muwrcvt w aanwhqmync aanwhqmync bppzfsncq 10 t jkky t z t t z z z t 10 qidkyca uhqubvbo kosyvh gsj gsj gsj duo jrro gsj jrro 10 lhktb lhktb lhktb uohl lhktb r lhktb lhktb wruim lhktb 10 e gqvdmpvxb gqvdmpvxb gqvdmpvxb sttirbhz gqvdmpvxb zdfpm ...
output:
30 60 15 35 20 20 23 12 38 44 8047
result:
ok 11 lines
Test #4:
score: 0
Accepted
time: 118ms
memory: 136816kb
input:
11 100 kalgqjh mdszzwe qxn kalgqjh hy kalgqjh suplvp r kkeoxmx tcoise suplvp suplvp y kalgqjh vrwniyici jmnyrradyq kalgqjh kalgqjh suplvp rkg xzevyk zc suplvp hcupv kalgqjh qakyahjaoi mum pbg u ip kalgqjh kalgqjh jngc ylr suplvp qxn kalgqjh bzwodm e kalgqjh kalgqjh evmm kbymvbccs kalgqjh suplvp kalg...
output:
12478 6722 9220 6668 4934 11233 7950 5470 4525 5743 1586066
result:
ok 11 lines
Test #5:
score: 0
Accepted
time: 27ms
memory: 139004kb
input:
2 1000 t lhijhkxzzx nhfiksblww h xg z dcbmbvyz ois ynwjgfp oqzv qtoinl gr teu kmza hs t mwhewk kjmuneon bekku qheweh szhagft fcwjp bobwnap y oqpole oqzv xeaiyhfeg rjkdidea wmeslege vyyi teomn yvmcnw vnvum tgnl swqqruuvc xxllevp bov dse e b rtbhogkx nzs e bs pppyndgrrv n tzbwqdusn e xeaiyhfeg i agnet...
output:
2430570 1904282
result:
ok 2 lines
Test #6:
score: -100
Wrong Answer
time: 788ms
memory: 136820kb
input:
503 16 yh yh yhc yhc yhcowdfqlwfidnx yhc yhc yh yhcowdfqlwfidn yhcowdfqlwfidnx yh h yh yhcowdfqlwfidnx yhcowdfqlwfidnx yhc 19 nb nbg vpfkllgv nmzqfsuafqtayjjjcidpygz nb nb gutq n omyuvm fgxtfbhuglxyiumi nbghjuti nbg nb fgxt nbghjuti n nb nbg n 7 rtjiwfidoahckhvgoxvvrncqvgerqiuaruiftakvugsgnsw wllcan...
output:
531 485 6 12 4 118 6 3 1635 18 373 20 954 6208 45 12 1124 79 267 2 5778 22 13 1 1 16 630 0 7 16315 0 2155 2308 26 936 109 103 5 0 2492 7 2 114 144 11 158 0 0 101 455 0 12234 78 631 5402 94 66 84 161 4412 5 3 81 22 20 13 52 632 6 137 56 2 3 64521 122 330 0 0 7 0 113 249 8 301 335 1825 110 4 108 50 12...
result:
wrong answer 91st lines differ - expected: '106', found: '12201!!!'