QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#719033 | #9406. Triangle | konyakest | RE | 21ms | 72612kb | C++17 | 6.9kb | 2024-11-06 22:10:11 | 2024-11-06 22:10:11 |
Judging History
answer
#include<bits/stdc++.h>
#define F(i,j,k) for(auto i=j;i<=(decltype(i))k;i++)
#define x first
#define y second
#define exec(...) [&](){__VA_ARGS__}()
#define endl '\n'
#define os ostream
#define pb push_back
#define view(x) begin(x),end(x)
#define lambda [&]
using namespace std;
using ll=long long;
template<typename T>void ckmin(T& x,T y){x=min(x,y);}
template<typename T>void ckmax(T& x,T y){x=max(x,y);}
#ifdef DEBUG
template<typename T1,typename T2>os& operator<<(os&,pair<T1,T2>);
template<typename T,typename=decltype(T().begin()),typename=enable_if_t<!is_same_v<decay_t<T>,string>>>os& operator<<(os& out,T x){auto n=0u;out<<"{";for(auto i:x) out<<i<<(++n==x.size()?"":",");return out<<"}";}
template<typename ...T>os& operator<<(os& out,tuple<T...> x){return apply(lambda(T... x){auto n=0u;out<<"{";((out<<x<<(++n==sizeof...(T)?"":",")),...);},x),out<<"}";}
template<typename T1,typename T2>os& operator<<(os& out,pair<T1,T2> x){return out<<tuple(x);}
#define debug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" = "<<std::make_tuple(__VA_ARGS__)<<endl
#else
#define debug(...) (void)0
#endif
const int maxn=1.3e6+5;
char s[maxn];
int n,h[maxn],id[maxn],sa[maxn],rk[maxn],buc[maxn],m,p,rk0[maxn];
int st[__lg(maxn)+5][maxn];
void getsa(){
m=130,p=0;
memset(buc,0,sizeof(int)*(m+3));
F(i,1,n) buc[ rk[i]=s[i] ]++;
F(i,1,m) buc[i]+=buc[i-1];
for(int i=n;i>=1;i--) sa[ buc[rk[i]]-- ]=i;
for(int w=1;p!=n;w*=2){
p=0;
F(i,1,n) if(i>=n-w+1) id[++p]=i;
F(i,1,n) if(sa[i]>w) id[++p]=sa[i]-w;
m=p;
memset(buc,0,sizeof(buc[0])*(m+3));
F(i,1,n) buc[ h[i]=rk[id[i]] ]++;
F(i,1,m) buc[i]+=buc[i-1];
for(int i=n;i>=1;i--) sa[ buc[h[i]]-- ]=id[i];
p=0,memcpy(rk0,rk,sizeof rk);
F(i,1,n) rk[sa[i]]=[w,x=sa[i-1],y=sa[i]](){return rk0[x]==rk0[y] && rk0[x+w]==rk0[y+w];}()? p: ++p;
}
F(_,1,n){
int i=rk[_];
st[0][i]=max(st[0][rk[_-1]]-1,0);
while(s[sa[i]+st[0][i]]==s[sa[rk[sa[i]]-1]+st[0][i]]) st[0][i]++;
}
F(i,1,__lg(n)) F(j,1,n-(1<<i)+1) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
F(i,1,n) debug(i,s+sa[i],st[0][i]);
}
int get(int x,int y){
if(x>y) return n-sa[y]+1;
int d=__lg(y-x+1);
return min(st[d][x],st[d][y-(1<<d)+1]);
}
int _lcp(int x,int y){
if(x==y) return n-y+1;
x=rk[x],y=rk[y];
if(x>y) swap(x,y);
return get(x+1,y);
}
int lcp(int x,int y){
return _lcp(x,y);
//int len=0;
//while(x+len-1<=n && y+len-1<=n && s[x+len]==s[y+len]) len++;
//assert(_lcp(x,y)==len);
//return len;
}
bool _cmp(pair<int,int> a,pair<int,int> b){
if(b.x>b.y) return 0;
if(a.x>a.y) return 1;
int len=lcp(a.x,b.x);
if(a.x+len<=a.y && b.x+len<=b.y) return s[a.x+len]<s[b.x+len];
return a.y-a.x < b.y-b.x;
}
bool cmp(pair<int,int> a,pair<int,int> b){
bool ans=_cmp(a,b);
assert(ans==(string(s+a.x,s+a.y+1)<string(s+b.x,s+b.y+1)));
return ans;
}
pair<int,int> mxstr(pair<int,int> a,pair<int,int> b){
return max(a,b,cmp);
}
ll ans;
int qzh[maxn];
int getfst(pair<int,int> rng){
if(rng.x>rng.y) return 0;
int len=rng.y-rng.x+1;
{
int l=1,r=rk[rng.x]-1,z=rk[rng.x];
while(l<=r){
int mid=(l+r)>>1;
if(get(mid+1,rk[rng.x])>=len) r=mid-1,z=mid;
else l=mid+1;
}
return z;
}
}
int getlst(pair<int,int> rng){
if(rng.x>rng.y) return 1;
int pos=sa[getfst(rng)];
int len=rng.y-rng.x+1;
rng={pos,pos+len-1};
{
int l=rk[rng.x]+1,r=n,z=n+1;
while(l<=r){
int mid=(l+r)>>1;
if(get(rk[rng.x]+1,mid)>=len && s[sa[mid]+len]=='$') l=mid+1;
else r=mid-1,z=mid;
}
return z;
}
}
int getoolst(pair<int,int> rng){
if(rng.x>rng.y) return 1;
int pos=sa[getfst(rng)];
int len=rng.y-rng.x+1;
rng={pos,pos+len-1};
{
int l=rk[rng.x]+1,r=n,z=n+1;
while(l<=r){
int mid=(l+r)>>1;
if(get(rk[rng.x]+1,mid)>=len) l=mid+1;
else r=mid-1,z=mid;
}
return z;
}
}
int _std_count1(pair<int,int> l,pair<int,int> r){//count how many str where s[l.x..l.y] < str < s[r.x..r.y]
int xl=getlst(l),xr=getfst(r)-1;
//debug(l,xl,r,xr);
if(xl>xr) return 0;
return qzh[xr]-qzh[xl-1];
}
int _std_count2(pair<int,int> l,pair<int,int> r){//count how many str where s[l.x..l.y] < str < s[r.x..r.y]
int xl=getlst(l),xr=getfst(r)-1;
debug(__func__,l,xl,r,xr);
if(xl>xr) return 0;
return qzh[xr]-qzh[xl-1];
}
vector<pair<int,int>> pp;
int _bf_count(pair<int,int> l,pair<int,int> r){
string s1=string(s+l.x,s+l.y+1),
s3=string(s+r.x,s+r.y+1);
int ans=0;
for(auto i:pp){
string s2=string(s+i.x,s+i.y+1);
if(s1<s2&&s2<s3) ans++;
}
return ans;
}
int count1(pair<int,int> l,pair<int,int> r){
//debug(l,r,_std_count(l,r),_bf_count(l,r));
//assert(_std_count(l,r)==_bf_count(l,r));
return _std_count1(l,r);
}
int count2(pair<int,int> l,pair<int,int> r){
//debug(l,r,_std_count(l,r),_bf_count(l,r));
//assert(_std_count(l,r)==_bf_count(l,r));
return _std_count2(l,r);
}
vector<size_t> hsh;
void solve(int l,int r){
debug("solve",l,r);
size_t cur=0;
//debug(ans);
int tmpqzh[n];
tmpqzh[l-1]=0;
F(i,l,r){
auto rng=equal_range(view(hsh),cur);
int B=distance(rng.x,rng.y);
int pos=getfst({l-1,i-1});
tmpqzh[i]=tmpqzh[i-1];
if(!B){(cur*=137)+=s[i];continue;}
debug(pos);
auto getoo=lambda(){
int L=l,R=i-1,z=i;
while(L<=R){
int mid=(L+R)>>1;
if(cmp({i,r},{l,mid})) z=mid,R=mid-1;
else L=mid+1;
}
debug(l,r,i,z,tmpqzh[i-1]-tmpqzh[z-1]);
debug(tmpqzh[i-1]-tmpqzh[z-1]);
return tmpqzh[i-1]-tmpqzh[z-1];
};
int C=count1(mxstr({l,i-1},{i,r}),{l,r})+
max(0,count1({i,r},{l,i-1})-getoo());
debug(i,r,l,i-1);
debug(l,i-1,i,r,B,C);
ans+=2ll*B*C;
if(C) tmpqzh[i]+=B;
debug(B,C,ans);
if(cmp({i,r},{l,i-1})) debug(i,r,l,i-1),ans+=1ll*B*(B-1);
(cur*=137)+=s[i];
debug(i,ans);
}
{
auto rng=equal_range(view(hsh),cur);
int B=distance(rng.x,rng.y);
if(B) ans+=1ll*(B-1)*qzh[getfst({l,r})-1];
}
debug(ans);
}
void doit(){
ans=0;
memset(s,0,sizeof(int)*(n+3));
memset(h,0,sizeof(int)*(n+3));
memset(qzh,0,sizeof(int)*(n+3));
memset(id,0,sizeof(int)*(n+3));
memset(sa,0,sizeof(int)*(n+3));
memset(rk,0,sizeof(int)*(n+3));
memset(buc,0,sizeof(int)*(n+3));
memset(rk0,0,sizeof(int)*(n+3));
for(auto& i:st) memset(i,0,sizeof(int)*(n+3));
hsh.clear();
n=0;
int p;
cin>>p;
pp.clear();
F(i,1,p){
char ss[maxn];
cin>>(ss+1);
int len=strlen(ss+1);
s[++n]='$';
F(j,1,len) s[++n]=ss[j];
pp.pb({n-len+1,n});
}
s[++n]='$';
s[++n]='|';
getsa();
for(auto i:pp){
size_t hsh=0;
F(j,i.x,i.y) (hsh*=137)+=s[j];
::hsh.pb(hsh);
}
sort(view(hsh));
for(auto i:pp) qzh[rk[i.x]]++;
F(i,1,n) qzh[i]+=qzh[i-1];
for(auto i:pp) solve(i.x,i.y);
int pre=0;
F(i,0,hsh.size()-1){
while(hsh[pre]!=hsh[i]) pre++;
int len=i-pre;
ans+=1ll*len*(len-1);
}
debug(ans);
cout<<ans/2<<endl;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin>>t;
while(t--) doit();
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 70396kb
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: 21ms
memory: 70692kb
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: 17ms
memory: 70692kb
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: 19ms
memory: 70372kb
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: 9ms
memory: 72612kb
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
Runtime Error
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...