QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#722965 | #9406. Triangle | AllenJYL | WA | 17ms | 43036kb | C++14 | 5.0kb | 2024-11-07 20:45:12 | 2024-11-07 20:45:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
#define all(_array) (_array).begin(),(_array).end()
#define msp(_array) memset(_array,0x3f,sizeof _array)
#define ms0(_array) memset(_array,0,sizeof _array)
#define msn(_array) memset(_array,-1,sizeof _array)
#define mc(_tar,_array) memcpy(_tar,_array,sizeof _tar)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define TAK cout<<"TAK"<<endl
#define NIE cout<<"NIE"<<endl
#define OK cerr<<"OK"<<endl
#define pii pair<int,int>
#define endl '\n'
bool bg_memory;
mt19937 rnd(time(0));
int Case=1;
// const int mod=1e9+7;
const int inf=1e18;
// const int bs=233;
const double eps=1e-6;
const int N=3e5+7,M=1e6+7;
template<class _t1,class _t2>inline void cmax(_t1 &a,_t2 b){a=a<b?b:a;}
template<class _t1,class _t2>inline void cmin(_t1 &a,_t2 b){a=a>b?b:a;}
inline int qp(int a,int b,int p){int res=1;while(b){if(b&1)res=1ll*res*a%p;a=1ll*a*a%p;b>>=1;}return res;}
inline int sqrt(int x,int r){int l=0,ans=0;while(l<=r){if(1ll*mid*mid<=x) ans=mid,l=mid+1;else r=mid-1;}return ans;}
int n;
int val[26];
int ans;
struct node{
string s;
vector<int> h[2];
}s[N];
struct hash{
int bs,mod;
int pw[M];
void clear(){
pw[0]=1;
for(int i=1;i<=1000000;i++) pw[i]=pw[i-1]*bs%mod;
}
void build(node&s,int id){
int ans=0;
s.h[id].push_back(0);
for(int i=0;i<s.s.size();i++) s.h[id].push_back(
ans=(1ll*ans*bs%mod+val[s.s[i]-'a'])%mod);
}
}h[2];
bool check(node a,node b,int l){
bool res=1;
for(int i=0;i<2;i++){
res&=((a.h[i][a.s.size()]-a.h[i][a.s.size()-l]*h[i].pw[l]%h[i].mod+h[i].mod)%h[i].mod==(b.h[i][b.s.size()]-b.h[i][b.s.size()-l]*h[i].pw[l]%h[i].mod+h[i].mod)%h[i].mod);
}
return res;
}
bool operator<(node a,node b){
int l=0,r=min(a.s.size(),b.s.size()),res=0;
// cerr<<a.s<<" "<<b.s<<" "<<res<<endl;
while(l<=r){
// cerr<<l<<" "<<r<<endl;
if(check(a,b,mid)) res=mid,l=mid+1;
else r=mid-1;
}
if(res==a.s.size()&&res==b.s.size()) return 0;
if(res==a.s.size()) return 1;
if(res==b.s.size()) return 0;
return a.s[a.s.size()-res-1]<b.s[b.s.size()-res-1];
}
unordered_map<int,vector<pii>> ap;
void Main(){
cin>>n;
ans=0;
ap.clear();
for(int i=0;i<26;i++) val[i]=rnd()%1145141919;
for(int i=1;i<=n;i++){
cin>>s[i].s;
reverse(all(s[i].s));
s[i].h[0].clear();
s[i].h[1].clear();
}
for(int i=1;i<=n;i++){
h[0].build(s[i],0);
h[1].build(s[i],1);
}
sort(s+1,s+n+1);
// for(int i=1;i<=n;i++) cout<<s[i].s<<endl;
for(int i=1;i<=n;i++){
string tmp="";
vector<int> h0,h1;
h0.push_back(0),h1.push_back(0);
int ht=(1ll*s[i].h[0].back()*h[0].bs%h[0].mod+s[i].h[1].back())%h[1].mod;
// cout<<ht<<endl;
for(int j=0;j<=s[i].s.size();j++){
int Tmp=(1ll*(s[i].h[0].back()-s[i].h[0][j]*h[0].pw[s[i].s.size()-j]%h[0].mod
+h[0].mod)%h[0].mod*h[0].bs%h[0].mod+(s[i].h[1].back()-s[i].h[1][j]*h[1].pw[s[i].s.size()-j]%h[1].mod
+h[1].mod)%h[1].mod)%h[1].mod;
// cout<<i<<" "<<j<<" "<<Tmp<<endl;
if(ap[Tmp].size()){
int pos=upper_bound(s+1,s+n+1,(node){tmp,{h0,h1}})-s;
int Pos=upper_bound(all(ap[Tmp]),(pii){pos,-114514})-ap[Tmp].begin();
ans+=(ap[Tmp].back().second-(Pos?ap[Tmp][Pos-1].second:0))-(ap[Tmp].size()-Pos)*pos;
// cout<<ap[Tmp].size()<<" "<<i<<" "<<j<<" "<<pos<<" "<<Pos<<endl;
}
if(j<s[i].s.size()){
tmp.push_back(s[i].s[j]);
h0.push_back((1ll*h0.back()*h[0].bs%h[0].mod+val[s[i].s[j]-'a'])%h[0].mod);
h1.push_back((1ll*h1.back()*h[1].bs%h[1].mod+val[s[i].s[j]-'a'])%h[1].mod);
}
}
ap[ht].push_back({i,(ap[ht].size()?ap[ht].back().second:0)+i});
}
cout<<ans<<endl;
return;
}
string RdFile="";
bool en_memory;
signed main(){
auto bg_clock=chrono::high_resolution_clock::now();
#ifdef ONLINE_JUDGE
// freopen((RdFile+".in").c_str(),"r",stdin);
// freopen((RdFile+".out").c_str(),"w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>Case;
h[0].mod=1226999999,h[0].bs=233;
h[1].mod=1000000007,h[1].bs=998244353;
h[0].clear(),h[1].clear();
while(Case--) Main();
auto en_clock=chrono::high_resolution_clock::now();
auto duration_clock=chrono::duration_cast<chrono::microseconds>(en_clock-bg_clock);
double duration_count=duration_clock.count()*0.001;
double memory_used=(&en_memory-&bg_memory)/1024.0/1024;
// cerr<<"Time:"<<duration_count<<"ms"<<endl;
// cerr<<"Memory: "<<memory_used<<"MB"<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 14ms
memory: 42712kb
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: 17ms
memory: 43036kb
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 11075
result:
wrong answer 14th lines differ - expected: '11081', found: '11075'