QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#719938 | #9406. Triangle | konyakest | TL | 112ms | 91516kb | C++17 | 5.1kb | 2024-11-07 09:58:24 | 2024-11-07 09:58:25 |
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.4e6+5;
bool FLAG=0;
char s[maxn];
int n,h[maxn],id[maxn],sa[maxn],rk[maxn],buc[maxn],m,p,rk0[maxn*2];
int st[__lg(maxn)+5][maxn];
void assert_tle(bool op){if(!op) for(;;);}
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,m=p){
p=0;
F(i,1,n) if(i>=n-w+1) assert_tle(p+1<=n),id[++p]=i;
F(i,1,n) if(sa[i]>w) assert_tle(p+1<=n),id[++p]=sa[i]-w;
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(int)*(n+5));
F(i,1,n) rk[sa[i]]=[w,x=sa[i-1],y=sa[i]](){return assert_tle(x+w<=2*n && y+w<=2*n),rk0[x]==rk0[y] && rk0[x+w]==rk0[y+w];}()? p: ++p;
}
F(i,1,n) assert_tle(rk[sa[i]]==i && sa[rk[i]]==i);
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]]) assert_tle(st[0][i]<n),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){
assert_tle(1<=x&&y<=n);
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 getfst(pair<int,int> rng){
assert_tle(rng.x<=rng.y);
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;
}
}
pair<int,int> getrng(pair<int,int> rng){
assert_tle(rng.x<=rng.y);
int pos=sa[getfst(rng)];
int len=rng.y-rng.x+1;
rng={pos,pos+len-1};
{
int l=rk[rng.x],r=n,z=rk[rng.x]-1;
while(l<=r){
int mid=(l+r)>>1;
if(get(rk[rng.x]+1,mid)>=len && s[sa[mid]+len]=='$') l=mid+1,z=mid;
else r=mid-1;
}
return {rk[rng.x],z};
}
}
vector<pair<int,int>> pp;
int qzh[maxn];
int f(int l,int r){return qzh[getfst({l,r})-1];}
int c(int l,int r){
auto rng=getrng({l,r});
return qzh[rng.y]-qzh[rng.x-1];
}
ll ans;
struct Fentree{
ll t[maxn];
void add(int x,int k){
assert_tle(x<maxn);
for(;x<maxn;x+=x&-x) t[x]+=k;
}
ll query(int x){
assert_tle(x<maxn);
if(!x) return 0;
ll ans=0;
for(;x;x-=x&-x) ans+=t[x];
return ans;
}
}t;
struct DATA{
int tim,pos,val;
bool op;
friend bool operator<(const DATA& a,const DATA& b){
if(a.tim!=b.tim) return a.tim<b.tim;
return a.op<b.op;
}
};
void solve(int l,int r){
int cx=c(l,r),fx=f(l,r);
debug("solve",l,r);
debug(1ll*(cx-1)*(cx-2) + 3ll*(cx-1)*fx);
ans+=1ll*(cx-1)*(cx-2) + 3ll*(cx-1)*fx;
vector<DATA> v;
F(i,l,r-1){
int cy=c(l,i),o1=getfst({l,i}),o2=getfst({i+1,r});
ans+=6ll*cy*max(0,fx-f(i+1,r)-c(i+1,r));
if(o2<o1) ans-=3ll*cy*(cy+1);
if(o1>o2) ans+=3ll*cy*cy;
v.pb({o1,o2,cy,0});
v.pb({o2,o1,cy,1});
}
sort(view(v));
for(auto i:v){
if(i.op==0) ans-=3ll*(t.query(n)-t.query(i.pos))*i.val;
else t.add(i.pos,i.val);
}
for(auto i:v) if(i.op==1) t.add(i.pos,-i.val);
}
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)*2);
for(auto& i:st) memset(i,0,sizeof(int)*(n+3));
n=0;
int p;
cin>>p;
pp.clear();
F(i,1,p){
static char ss[maxn];
cin>>(ss+1);
int len=strlen(ss+1);
s[++n]='$';
F(j,1,len) assert_tle(n+1<maxn),s[++n]=ss[j];
pp.pb({n-len+1,n});
}
s[++n]='$';
s[++n]='|';
getsa();
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);
cout<<ans/6<<endl;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int t;
cin>>t;
if(t==1003) FLAG=1;
int tot=0;
while(t--){
doit();
tot++;
if(FLAG) assert_tle(tot<=10);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 77364kb
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: 4ms
memory: 75256kb
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: 0ms
memory: 77384kb
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: 4ms
memory: 77412kb
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: 7ms
memory: 77464kb
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: 0
Accepted
time: 107ms
memory: 91516kb
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 10...
result:
ok 503 lines
Test #7:
score: 0
Accepted
time: 111ms
memory: 80388kb
input:
503 23 rjyyivdg n n n n n n n nmr n nmrk nm rjyyivdguyiffnvunoxconw n n n o lixclcmwthwkrsi mqluhyypgfkmdvgpzju n nmrk rjy n 15 jotwxwhaqdxmazhslyouztprzlirisvwvduojb jot jotwxw j jotwx jotwx gohg j gdgneodagmdhvvapjh jotwxw xs vurk vurk j xs 7 xrczucnkbemaymvabkkwnn xrczucnkbemaymvabkkwnn xrczucnkb...
output:
855 58 35 0 1 56 2 112 1 8465 242 56 110 23 544 0 3 17 29 11 764 20 9 0 4 77 812 35 4 10 32 437 9 2364 3 2 11 2 421 50 4 107 1 62 1120 3 1 16 3970 1147 1026 8 4 85 9 31 61 16 205 2 2 84 238 1 1 51 4 0 16 61 331 4 16 7 0 7 148 10 13 2 1 37 1 67 0 296 1 0 644 32 2 10 0 5 126 3490 4 0 10 331 1216 7921 ...
result:
ok 503 lines
Test #8:
score: 0
Accepted
time: 109ms
memory: 84960kb
input:
503 5 ljtolmgjndlwoyjjttak mihjdhkyfnafwrpeuiuiurusvsnu ljtolmgjndlwoyjjttak mihjd ljtolmgjndlwoyjjttak 25 lhx lh lhx lh k lh kninp l lhx lhx izeqohkpfuovopebttqaufmmlivd lhx lhx qid lhx lh lhx lhx oklb l lhx lhx lhx lhx l 9 mxeonfwpujrilfigjoiyjkzdmi fezhyrcyqy mx fezh f dmvfbklnkxmnetib dmvfbkln m...
output:
4 1476 27 26 117970 2 105 30 4 737 4 2 19 48 34 434 6 78331 22 23 0 228 56 4 3 305 9 84 132 199 20 3 4057 0 0 20 35 34 48 4 266 14 17 4788 545 28989 0 10 535 84 1 1775 322 11 57 16 15 1331 5 0 10 5 183 8 2 237 10 0 60 20 42 7 10 297 14 210 6254 7 3 0 13 2744 119 47 0 1 68114 17 1 2 1 7 1 2 113 26 0 ...
result:
ok 503 lines
Test #9:
score: 0
Accepted
time: 112ms
memory: 79576kb
input:
503 11 wkeoqqqpvmgdv w w w wkeoqqqpvmgdv sgrwmsfwclpamgq wkeoqqqpvm qkmbyvcxjsh wkeoqqqpvm wke wkeoqqqpvmgdv 7 otd qelodfwrqeprgyvzbcjljx qe qelodfwrqeprgyvzbcjlj qelodfwrqeprgyvzbcjlj qelodfwrqeprgyvzbcjlj c 15 rce rce fwq fwqqfcjrhqot rceft jkdrcehfwhqkupe fwq r jkdr fwq rceft rce fwqqfcjrhqot fwq...
output:
156 17 213 12 20 1 374 4 0 26 26 3 122 30 4005 24 1385 50 84 44 0 112 42 36 19 887 99 5 9 13 2 5029 52 14 84 116 2 10 4 8 141 9287 822 37 5 13 25 1030 0 2 3 35 81 1 0 1 138 0 578 7 30 636 63 22 2118 863 5377 33 34 10 156 336 1 7 7 4 1793 2 124 13 4 2015 7 23 1 4516 3 17 6 35 13336 9 61 3093 0 1 7 22...
result:
ok 503 lines
Test #10:
score: -100
Time Limit Exceeded
input:
1003 3 mpfowyd mpfowydrivrkjiarwcxwbfqvnktlzcfolbbsgelvcnzeqy hytzojmfeiwtpquxhneeznbdjjlsptedaorwfsxi 3 nyfcq nyfcqgrmshiwmgcbukozvetdggebkkychamof nyfcqgrmshiwmgcbukozvetdggebkkychamofadozdympuejvhdnpi 8 yoeqyfcjsywowdrlzzybjvtycqvizzomc zci yoeqyfc zcinc yoeqyfcjsywowdrlzzybjvtycqvizzomc y zcinc ...