QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#298219 | #7901. Basic Substring Structure | ucup-team266# | WA | 22ms | 8196kb | C++14 | 4.4kb | 2024-01-05 20:32:25 | 2024-01-05 20:32:26 |
Judging History
answer
/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest
9. module on time
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
int n,s[200005];
struct BIT
{
int t[200005];
void init()
{
for(int i=1;i<=n;i++) t[i]=0;
}
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int d)
{
for(int i=x;i<=n;i+=lowbit(i)) t[i]+=d;
}
int query(int x)
{
int res=0;
for(int i=x;i>=1;i-=lowbit(i)) res+=t[i];
return res;
}
}bt,bt2;
int upd_pos,upd_val;
struct Hashing
{
int mod,bse;
int pw[200005];
int H1[200005];
void init(int M,int B)
{
mod=M,bse=B;
pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=1LL*pw[i-1]*bse%mod;
for(int i=1;i<=n;i++) H1[i]=1LL*bse*H1[i-1]%mod+(s[i]),H1[i]%=mod;
}
int query(int l,int r)
{
int re=(H1[r]-1LL*H1[l-1]*pw[r-l+1]%mod+mod)%mod;
if(l<=upd_pos&&upd_pos<=r)
{
int wei=r-upd_pos;
re=(re-pw[wei]*s[upd_pos]%mod+mod)%mod;
re=(re+pw[wei]*upd_val)%mod;
}
return re;
}
}h1,h2;
int chkequ(int l1,int r1,int l2,int r2)
{
if(h1.query(l1,r1)!=h1.query(l2,r2)) return 0;
return h2.query(l1,r1)==h2.query(l2,r2);
}
int ans[200005];
vector <pii > buc[200005];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>s[i],ans[i]=0,buc[i].clear();
h1.init(998244853,19260817);
h2.init(1e9+7,1919810);
bt.init();
for(int i=2;i<=n;i++)
{
int l=1,r=n-i+1,res=0;
upd_pos=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(chkequ(1,mid,i,i+mid-1)) res=mid,l=mid+1;
else r=mid-1;
}
// cout<<"z: "<<i<<" "<<res<<"\n";
// case 1: outsize [1,z[i]] and [i,i+z[i]-1]
if(res+1<=i-1) bt.update(res+1,res),bt.update(i,-res);
// cout<<"... "<<bt.query(2)<<"\n";
if(i+res<=n) bt.update(i+res,res);
// case 2: i+z[i] or z[i]+1
if(res<n-i+1)
{
int j=i+res+1;
l=1,r=n-j+1;
int res2=0;
upd_pos=j-1,upd_val=s[res+1];
while(l<=r)
{
int mid=(l+r)>>1;
if(chkequ(res+2,res+2+mid-1,j,j+mid-1)) res2=mid,l=mid+1;
else r=mid-1;
}
// cout<<i<<" -> "<<j-1<<"\n";
buc[j-1].pb(mp(s[res+1],res2+1));
if(res+1>=i) continue;
upd_pos=res+1,upd_val=s[i+res];
l=1,r=n-j+1;
res2=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(chkequ(res+2,res+2+mid-1,j,j+mid-1)) res2=mid,l=mid+1;
else r=mid-1;
}
// cout<<i<<" -> "<<res+1<<"\n";
buc[res+1].pb(mp(s[i+res],res2+1));
}
}
for(int i=1;i<=n;i++) ans[i]+=bt.query(i);//,cout<<ans[i]<<" ";
// cout<<"\n";
bt.init(),bt2.init();
// case 3: in [i,i+z[i]-1]
for(int i=2;i<=n;i++)
{
int l=1,r=n-i+1,res=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(chkequ(1,mid,i,i+mid-1)) res=mid,l=mid+1;
else r=mid-1;
}
if(res)
{
bt.update(i,1),bt.update(i+res,-1);
bt2.update(i,i),bt2.update(i+res,-i);
}
}
for(int i=1;i<=n;i++) ans[i]+=i*bt.query(i)-bt2.query(i);
// case 4: in[1,z[i]]
bt.init(),bt2.init();
for(int i=2;i<=n;i++)
{
int l=1,r=n-i+1,res=0;
upd_pos=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(chkequ(1,mid,i,i+mid-1)) res=mid,l=mid+1;
else r=mid-1;
}
if(res<=i)
{
bt.update(1,1),bt.update(res+1,-1);
bt2.update(1,1),bt2.update(res+1,-1);
}
else
{
bt.update(1,1),bt.update(i,-1);
bt2.update(1,1),bt2.update(i,-1);
}
}
for(int i=1;i<=n;i++) ans[i]+=i*bt.query(i)-bt2.query(i);
// for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
// cout<<"\n";
int Ans=0;
// cout<<"\n";
for(int i=1;i<=n;i++)
{
sort(buc[i].begin(),buc[i].end());
int maxx=0;
for(int j=0;j<buc[i].size();j++)
{
int k=j,res=0;
while(k<buc[i].size()&&buc[i][k].fi==buc[i][j].fi) res+=buc[i][k].se,k++;
// cout<<i<<": "<<buc[i][j].fi<<" "<<res<<"\n";
k--,j=k;
maxx=max(maxx,res);
}
ans[i]+=maxx+n;
Ans+=(ans[i]^i);
// cout<<i<<": "<<ans[i]<<"\n";
}
cout<<Ans<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int _=1;
cin>>_;
while(_--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 8188kb
input:
2 4 2 1 1 2 12 1 1 4 5 1 4 1 9 1 9 8 10
output:
15 217
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 22ms
memory: 8196kb
input:
10000 8 2 1 2 1 1 1 2 2 9 2 2 1 2 1 2 1 2 1 15 2 1 2 1 1 1 1 2 2 1 2 1 2 2 1 2 1 1 10 2 1 1 1 2 2 1 1 2 2 3 2 1 2 11 1 2 2 1 1 2 1 2 2 1 1 14 2 1 1 1 1 2 1 1 1 2 2 1 2 1 12 2 2 2 1 2 2 2 1 1 2 1 2 4 2 1 1 2 8 1 2 2 2 1 2 1 1 8 1 1 2 1 2 1 1 1 6 2 1 1 1 2 2 14 2 2 1 1 1 1 2 2 2 1 2 2 1 1 10 1 2 2 1 1...
output:
94 166 371 3 211 9 265 369 283 15 95 114 58 334 225 3 367 364 377 316 3 19 124 61 16 81 42 261 11 77 28 90 80 109 225 194 20 42 219 63 112 19 34 71 316 362 291 310 355 281 302 287 231 312 3 330 54 297 3 72 32 141 322 39 338 90 242 3 169 329 204 19 155 3 416 393 392 76 270 365 19 54 20 287 3 17 351 3...
result:
wrong answer 2nd lines differ - expected: '128', found: '166'