QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#723063#9406. TriangleAllenJYLWA 15ms42820kbC++144.7kb2024-11-07 21:05:322024-11-07 21:05:33

Judging History

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

  • [2024-11-07 21:05:33]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:42820kb
  • [2024-11-07 21:05:32]
  • 提交

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();
        // 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;
            // 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;
            }
            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: 7ms
memory: 42764kb

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: 15ms
memory: 42820kb

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'