#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
unsigned int n,m;
const unsigned int maxn=1000000+10;
unsigned int all[maxn],allb[maxn],hashn=0,base2=3427793,hashn2=0,mod2=987432683,mod=1e9+7,base=3427903,mp[maxn],smp[maxn];
char c;
void fastscan(unsigned int &nu)
{
nu = 0;
c = getchar();
for (; (c>47 && c<58); c=getchar())
nu = nu *10 + c - 48;
}
/*inline unsigned int ww2(unsigned int a){
if(a>=mod2){
a-=mod2;
}
return a;
}*/
inline unsigned int ww(unsigned int a){
if(a>=mod)
{
a-=mod;
}
return a;
}
inline void aval(){
mp[0]=1;
smp[0]=0;
smp[1]=1;
for(unsigned int i=1;i<maxn-1;i++){
mp[i]=1ll*mp[i-1]*base%mod;
smp[i+1]=ww(smp[i]+mp[i]);
}
// mp2[0]=1;
// smp2[0]=0;
// smp2[1]=1;
// for(unsigned int i=1;i<maxn-1;i++){
// mp2[i]=1ll*mp2[i-1]*base2%mod2;
// smp2[i+1]=ww2(smp2[i]+mp2[i]);
// }
}
unsigned int kaf=(1<<20);
struct segment{
struct node{
unsigned int len,hash,lazy;
//unsigned int hash2;
node(){
len=hash=lazy=0;
//hash2=0;
}
};
node seg[(1<<21)];
inline node merge(node a,node b){
if(a.lazy!=0){
if(a.len==0){
//hehe;
}
else if(a.len==1){
a.hash+=mod-a.lazy;
a.hash=ww(a.hash);
}
else{
a.hash+=mod-(1ll*smp[a.len]*a.lazy%mod);
a.hash=ww(a.hash);
}
// a.hash2+=mod2-(1ll*smp2[a.len]*a.lazy%mod2);
// a.hash2=ww2(a.hash2);
a.lazy=0;
}
if(b.len==0){
return a;
}
if(b.lazy!=0){
if(b.len==1){
b.hash+=mod-b.lazy;
b.hash=ww(b.hash);
}
else{
b.hash+=mod-(1ll*smp[b.len]*b.lazy%mod);
b.hash=ww(b.hash);
}
// b.hash2+=mod2-(1ll*smp2[b.len]*b.lazy%mod2);
// b.hash2=ww2(b.hash2);
b.lazy=0;
}
if(a.len==0){
return b;
}
a.hash=1ll*a.hash*mp[b.len]%mod;
a.hash+=b.hash;
a.hash=ww(a.hash);
//a.hash2=1ll*a.hash2*mp2[b.len]%mod2;
//a.hash2+=b.hash2;
//a.hash2=ww2(a.hash2);
a.len+=b.len;
return a;
}
inline void calc(unsigned int i){
if(i>=kaf){
if(seg[i].lazy==0){
return ;
}
if(seg[i].len==0){
seg[i].lazy=seg[i].hash=0;
//seg[i].hash2=0;
return ;
}
seg[i].hash+=mod-seg[i].lazy;
seg[i].hash=ww(seg[i].hash);
// seg[i].hash2+=mod2-seg[i].lazy;
// seg[i].hash2=ww2(seg[i].hash2);
return ;
}
seg[i]=merge(seg[(i<<1)],seg[(i<<1)^1]);
}
inline void shift(unsigned int i){
if(i>=kaf){
return calc(i);
}
if(seg[i].lazy==0)
{
return ;
}
seg[(i<<1)].lazy+=seg[i].lazy;
seg[(i<<1)^1].lazy+=seg[i].lazy;
seg[i].lazy=0;
return ;
}
void ins(unsigned int i,unsigned int l,unsigned int r,unsigned int tl,unsigned int w){
if(l>r||l>tl||r<tl){
return ;
}
if(l>=tl&&r<=tl){
if(w==0){
seg[i].len=0;
seg[i].hash=0;
// seg[i].hash2=0;
seg[i].lazy=0;
}
else{
seg[i].len=1;
seg[i].hash=w;
// seg[i].hash2=w;
seg[i].lazy=0;
}
//cout<<l<<" ins "<<r<<" "<<w<<" "<<seg[i].hash<<"\n";
return ;
}
shift(i);
unsigned int m=(l+r)>>1;
if(tl<=m){
ins((i<<1),l,m,tl,w);
}
else{
ins((i<<1)^1,m+1,r,tl,w);
}
calc(i);
}
void upd(unsigned int i,unsigned int l,unsigned int r,unsigned int tl,unsigned int tr){
if(l>r||l>tr||r<tl||tl>tr){
return ;
}
if(l>=tl&&r<=tr){
// calc(i);
seg[i].lazy++;
return ;
}
shift(i);
unsigned int m=(l+r)>>1;
upd((i<<1),l,m,tl,tr);
upd((i<<1)^1,m+1,r,tl,tr);
calc(i);
}
unsigned int pors(){
//if(seg[1].hash==hashn&&seg[1].hash2==hashn2){
if(seg[1].hash==hashn){
return 1;
}
return 0;
}
}seg;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
aval();
fastscan(n);
fastscan(m);
unsigned int fn=n-1;
for(unsigned int i=0;i<n;i++){
fastscan(all[i]);
//cin>>all[i];
//hashn2+=1ll*mp2[fn]*all[i]%mod2;
hashn+=1ll*mp[fn]*all[i]%mod;
//hashn2=ww2(hashn2);
hashn=ww(hashn);
fn--;
}
for(unsigned int i=0;i<m;i++){
fastscan(allb[i]);
//cin>>allb[i];
}
vector<int>res;
for(unsigned int i=0;i<m;i++){
//cout<<i<<" "<<seg.seg[1].hash<<"\n";
if(i>=n){
unsigned int p=allb[i-n];
seg.ins(1,0,kaf-1,p,0);
// seg.upd(1,0,kaf-1,0,m+1);
seg.seg[1].lazy++;
}
unsigned int p=allb[i];
seg.ins(1,0,kaf-1,p,min(n,i+1));
if(i>=n-1){
if(seg.pors()){
res.push_back(i+1-n+1);
}
}
}
int sz=(int)res.size();
cout<<sz<<"\n";
for(auto x:res){
cout<<x<<" ";
}
cout<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
35516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
35512 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
35520 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
35416 KB |
Output is correct |
| 2 |
Correct |
24 ms |
35508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
35420 KB |
Output is correct |
| 2 |
Correct |
23 ms |
35512 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
35420 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
37560 KB |
Output is correct |
| 2 |
Correct |
118 ms |
38996 KB |
Output is correct |
| 3 |
Incorrect |
25 ms |
39720 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
37808 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
39336 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
37848 KB |
Output is correct |
| 2 |
Correct |
126 ms |
38996 KB |
Output is correct |
| 3 |
Incorrect |
25 ms |
39248 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
39504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
39608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
37468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
188 ms |
37572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
