QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #618646 | #7901. Basic Substring Structure | hwpvector | Compile Error | / | / | C++20 | 5.9kb | 2024-10-07 02:00:26 | 2024-10-07 02:00:27 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=2e5+10;
int n,f[N],z[N],s[N],d[N];
map<int,int> mp[N];
int lowbit(int x) {return x&-x;}
void add(int x,int v) {while (x<=n) f[x]+=v,x+=lowbit(x);}
int query(int x) {int ans=0; while (x>0) ans+=f[x],x-=lowbit(x); return ans;}
void update(int l,int r,int v) {add(l,v),add(r+1,-v);}
struct Bart{
int I,m;
void ini(int Mod) {m=Mod; I=(1ll<<62)/m;}
int operator()(int x) {
int tp=x-((__int128)x*I>>62)*m;
while (tp>=m) tp-=m;
while (tp<0) tp+=m;
return tp;
}
};
struct hash{
int base,mod;
Bart getmod;
int p[N],h[N];
void init(int Base,int Mod) {
base=Base,mod=Mod; getmod.ini(mod); p[0]=1;
for (int i=1;i<=n;i++) p[i]=getmod(p[i-1]*base);
for (int i=1;i<=n;i++) h[i]=getmod(h[i-1]*base+(s[i]^114514));
}
int gethash(int l,int r,int pos,int u,int v) {
int hash=getmod(h[r]-h[l-1]*p[r-l+1]);
u=u^114514,v=v^114514;
if (l<=pos&&pos<=r) {
hash-=getmod(u*p[r-pos]); hash+=getmod(v*p[r-pos]);
hash=getmod(hash);
} return hash;
}
}h[2];
bool equ(int l1,int r1,int l2,int r2,int pos,int u,int v) {
return h[0].gethash(l1,r1,pos,u,v)==h[0].gethash(l2,r2,pos,u,v)&&h[1].gethash(l1,r1,pos,u,v)==h[1].gethash(l2,r2,pos,u,v);
}
void solve() {
cin>>n;
for (int i=1;i<=n;i++) cin>>s[i],f[i]=0;
z[1]=n; h[0].init(402653189,1e9+7); h[1].init(998244353,1610612741);
for (int i=2,l=0,r=0;i<=n;i++) {
if (i<=r) z[i]=min(z[i-l+1],r-i+1); else z[i]=0;
while (i+z[i]<=n&&s[i+z[i]]==s[z[i]+1]) ++z[i];
if (i+z[i]-1>r) l=i,r=i+z[i]-1;
}
// for (int i=1;i<=n;i++) cout<<z[i]<<' '; cout<<'\n';
int sum=0; for (int i=1;i<=n;i++) sum+=z[i];
for (int i=2;i<=n;i++) {
if (z[i]) {
update(i,i,z[i]),update(i+1,i+z[i],-1);
if (i<=z[i]) update(1,1,z[i]),update(2,i-1,-1),update(i,i,-z[i]+i-2);
else update(1,1,z[i]),update(2,1+z[i],-1);
}
if (i+z[i]-1==n) continue;
int v1=s[i+z[i]],v2=s[z[i]+1],lcp;
s[z[i]+1]=v1;
if (i+z[i]+1>n||s[z[i]+2]!=s[i+z[i]+1]) lcp=0;
else {
int l=0,r=n-(i+z[i]+1);
int s1=z[i]+2,s2=i+z[i]+1;
while (l<r) {
int mid=r-((r-l)>>1);
if (equ(s1,s1+mid,s2,s2+mid,z[i]+1,v2,v1)) l=mid;
else r=mid-1;
}
lcp=l+1;
}
s[z[i]+1]=v2; mp[z[i]+1][v1]+=lcp+1;
// cout<<z[i]+1<<' '<<v1<<' '<<lcp<<'\n';
s[i+z[i]]=v2;
if (i+z[i]+1>n||s[z[i]+2]!=s[i+z[i]+1]) lcp=0;
else {
int l=0,r=n-(i+z[i]+1);
int s1=z[i]+2,s2=i+z[i]+1;
while (l<r) {
int mid=r-((r-l)>>1);
if (equ(s1,s1+mid,s2,s2+mid,i+z[i],v1,v2)) l=mid;
else r=mid-1;
}
lcp=l+1;
}
s[i+z[i]]=v1; mp[i+z[i]][v2]+=lcp+1;
}
for (int i=1;i<=n;i++) d[i]=d[i-1]+query(i);
int ans=0;
for (int i=1;i<=n;i++) {
int mx=0;
for (auto [c,v]:mp[i]) mx=max(mx,v); mp[i].clear();
// cout<<mx<<' ';
ans+=(sum+mx-d[i])^i;
} cout<<ans<<'\n';
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int T; cin>>T; while (T--) solve();
}#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=2e5+10;
int n,f[N],z[N],s[N],d[N];
map<int,int> mp[N];
int lowbit(int x) {return x&-x;}
void add(int x,int v) {while (x<=n) f[x]+=v,x+=lowbit(x);}
int query(int x) {int ans=0; while (x>0) ans+=f[x],x-=lowbit(x); return ans;}
void update(int l,int r,int v) {add(l,v),add(r+1,-v);}
struct Bart{
int I,m;
void ini(int Mod) {m=Mod; I=(1ll<<62)/m;}
int operator()(int x) {
int tp=x-((__int128)x*I>>62)*m;
while (tp>=m) tp-=m;
while (tp<0) tp+=m;
return tp;
}
};
struct hash{
int base,mod;
Bart getmod;
int p[N],h[N];
void init(int Base,int Mod) {
base=Base,mod=Mod; getmod.ini(mod); p[0]=1;
for (int i=1;i<=n;i++) p[i]=getmod(p[i-1]*base);
for (int i=1;i<=n;i++) h[i]=getmod(h[i-1]*base+(s[i]^114514));
}
int gethash(int l,int r,int pos,int u,int v) {
int hash=getmod(h[r]-h[l-1]*p[r-l+1]);
u=u^114514,v=v^114514;
if (l<=pos&&pos<=r) {
hash-=getmod(u*p[r-pos]); hash+=getmod(v*p[r-pos]);
hash=getmod(hash);
} return hash;
}
}h[2];
bool equ(int l1,int r1,int l2,int r2,int pos,int u,int v) {
return h[0].gethash(l1,r1,pos,u,v)==h[0].gethash(l2,r2,pos,u,v)&&h[1].gethash(l1,r1,pos,u,v)==h[1].gethash(l2,r2,pos,u,v);
}
void solve() {
cin>>n;
for (int i=1;i<=n;i++) cin>>s[i],f[i]=0;
z[1]=n; h[0].init(10000609,1e9+7); h[1].init(10000877,1e9+9);
for (int i=2,l=0,r=0;i<=n;i++) {
if (i<=r) z[i]=min(z[i-l+1],r-i+1); else z[i]=0;
while (i+z[i]<=n&&s[i+z[i]]==s[z[i]+1]) ++z[i];
if (i+z[i]-1>r) l=i,r=i+z[i]-1;
}
// for (int i=1;i<=n;i++) cout<<z[i]<<' '; cout<<'\n';
int sum=0; for (int i=1;i<=n;i++) sum+=z[i];
for (int i=2;i<=n;i++) {
if (z[i]) {
update(i,i,z[i]),update(i+1,i+z[i],-1);
if (i<=z[i]) update(1,1,z[i]),update(2,i-1,-1),update(i,i,-z[i]+i-2);
else update(1,1,z[i]),update(2,1+z[i],-1);
}
if (i+z[i]-1==n) continue;
int v1=s[i+z[i]],v2=s[z[i]+1],lcp;
s[z[i]+1]=v1;
if (i+z[i]+1>n||s[z[i]+2]!=s[i+z[i]+1]) lcp=0;
else {
int l=0,r=n-(i+z[i]+1);
int s1=z[i]+2,s2=i+z[i]+1;
while (l<r) {
int mid=r-((r-l)>>1);
if (equ(s1,s1+mid,s2,s2+mid,z[i]+1,v2,v1)) l=mid;
else r=mid-1;
}
lcp=l+1;
}
s[z[i]+1]=v2; mp[z[i]+1][v1]+=lcp+1;
// cout<<z[i]+1<<' '<<v1<<' '<<lcp<<'\n';
s[i+z[i]]=v2;
if (i+z[i]+1>n||s[z[i]+2]!=s[i+z[i]+1]) lcp=0;
else {
int l=0,r=n-(i+z[i]+1);
int s1=z[i]+2,s2=i+z[i]+1;
while (l<r) {
int mid=r-((r-l)>>1);
if (equ(s1,s1+mid,s2,s2+mid,i+z[i],v1,v2)) l=mid;
else r=mid-1;
}
lcp=l+1;
}
s[i+z[i]]=v1; mp[i+z[i]][v2]+=lcp+1;
}
for (int i=1;i<=n;i++) d[i]=d[i-1]+query(i);
int ans=0;
for (int i=1;i<=n;i++) {
int mx=0;
for (auto [c,v]:mp[i]) mx=max(mx,v); mp[i].clear();
// cout<<mx<<' ';
ans+=(sum+mx-d[i])^i;
} cout<<ans<<'\n';
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int T; cin>>T; while (T--) solve();
}
Details
answer.code:110:2: error: stray ‘#’ in program
110 | }#include <bits/stdc++.h>
| ^
answer.code:110:12: error: ‘bits’ was not declared in this scope
110 | }#include <bits/stdc++.h>
| ^~~~
answer.code:110:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
110 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:110:12: error: ‘bits’ was not declared in this scope
110 | }#include <bits/stdc++.h>
| ^~~~
answer.code:110:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
110 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:110:12: error: ‘bits’ was not declared in this scope
110 | }#include <bits/stdc++.h>
| ^~~~
answer.code:110:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
110 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:110:12: error: ‘bits’ was not declared in this scope
110 | }#include <bits/stdc++.h>
| ^~~~
answer.code:110:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
110 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:110:12: error: ‘bits’ was not declared in this scope
110 | }#include <bits/stdc++.h>
| ^~~~
answer.code:110:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
110 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:110:12: error: ‘bits’ was not declared in this scope
110 | }#include <bits/stdc++.h>
| ^~~~
answer.code:110:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
110 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:110:12: error: ‘bits’ was not declared in this scope
110 | }#include <bits/stdc++.h>
| ^~~~
answer.code:110:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
110 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:110:12: error: ‘bits’ was not declared in this scope
110 | }#include <bits/stdc++.h>
| ^~~~
answer.code:110:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
110 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:110:12: error: ‘bits’ was not declared in this scope
110 | }#include <bits/stdc++.h>
| ^~~~
answer.code:110:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
110 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:110:3: error: ‘include’ does not name a type
110 | }#include <bits/stdc++.h>
| ^~~~~~~
answer.code:115:11: error: redefinition of ‘const long long int N’
115 | const int N=2e5+10;
| ^
answer.code:6:11: note: ‘const long long int N’ previously defined here
6 | const int N=2e5+10;
| ^
answer.code:116:5: error: redefinition of ‘long long int n’
116 | int n,f[N],z[N],s[N],d[N];
| ^
answer.code:7:5: note: ‘long long int n’ previously declared here
7 | int n,f[N],z[N],s[N],d[N];
| ^
answer.code:116:7: error: redefinition of ‘long long int f [200010]’
116 | int n,f[N],z[N],s[N],d[N];
| ^
answer.code:7:7: note: ‘long long int f [200010]’ previously declared here
7 | int n,f[N],z[N],s[N],d[N];
| ^
answer.code:116:12: error: redefinition of ‘long long int z [200010]’
116 | int n,f[N],z[N],s[N],d[N];
| ^
answer.code:7:12: note: ‘long long int z [200010]’ previously declared here
7 | int n,f[N],z[N],s[N],d[N];
| ^
answer.code:116:17: error: redefinition of ‘long long int s [200010]’
116 | int n,f[N],z[N],s[N],d[N];
| ^
answer.code:7:17: note: ‘long long int s [200010]’ previously declared here
7 | int n,f[N],z[N],s[N],d[N];
| ^
answer.code:116:22: error: redefinition of ‘long long int d [200010]’
116 | int n,f[N],z[N],s[N],d[N];
| ^
answer.code:7:22: note: ‘long long int d [200010]’ previously declared here
7 | int n,f[N],z[N],s[N],d[N];
| ^
answer.code:117:14: error: redefinition of ‘std::map<long long int, long long int> mp [200010]’
117 | map<int,int> mp[N];
| ^~
answer.code:8:14: note: ‘std::map<long long int, long long int> mp [200010]’ previously declared here
8 | map<int,int> mp[N];
| ^~
answer.code:119:5: error: redefinition of ‘long long int lowbit(long long int)’
119 | int lowbit(int x) {return x&-x;}
| ^~~~~~
answer.code:10:5: note: ‘long long int lowbit(long long int)’ previously defined here
10 | int lowbit(int x) {return x&-x;}
| ^~~~~~
an...