This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define DIM 1000010
#define MOD1 1000000007
#define MOD2 1000000009
#define B 1000000
using namespace std;
struct segment_tree{
long long hash1,hash2,cnt;
} aint[DIM*4];
map <int,int> nrm;
int v[DIM],w[DIM];
long long p1[DIM],p2[DIM];
vector <int> sol;
int n,m,i,j,x;
void update (int nod, int st, int dr, int poz, int val){
if (st == dr){
aint[nod].hash1 = aint[nod].hash2 = val;
if (val)
aint[nod].cnt = 1;
else aint[nod].cnt = 0;
return;
}
int mid = (st+dr)>>1;
if (poz <= mid)
update (nod<<1,st,mid,poz,val);
else update ((nod<<1)|1,mid+1,dr,poz,val);
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
aint[nod].hash1 = (aint[fiu_st].hash1 * p1[ aint[fiu_dr].cnt ] % MOD1 + aint[fiu_dr].hash1) % MOD1;
aint[nod].hash2 = (aint[fiu_st].hash2 * p2[ aint[fiu_dr].cnt ] % MOD2 + aint[fiu_dr].hash2) % MOD2;
aint[nod].cnt = aint[fiu_st].cnt + aint[fiu_dr].cnt;
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>m>>n;
long long hash1 = 0, hash2 = 0;
for (i=1;i<=m;i++){
cin>>x;
hash1 = (hash1 * B % MOD1 + x) % MOD1;
hash2 = (hash2 * B % MOD2 + x) % MOD2;
}
p1[0] = p2[0] = 1;
for (i=1;i<=n;i++){
p1[i] = p1[i-1] * B % MOD1;
p2[i] = p2[i-1] * B % MOD2;
}
for (i=1;i<=n;i++){
cin>>v[i];
w[i] = v[i];
}
sort (w+1,w+n+1);
for (i=1;i<=n;i++)
nrm[w[i]] = i;
for (i=1;i<m;i++)
update (1,1,n,nrm[v[i]],i);
long long sum1 = 0, sum2 = 0;
for (i=0;i<m;i++){
sum1 = (sum1 + p1[i]) % MOD1;
sum2 = (sum2 + p2[i]) % MOD2;
}
for (i=m;i<=n;i++){
/// adaug elem asta
update (1,1,n,nrm[v[i]],i);
long long val1 = (aint[1].hash1 - sum1 * (i-m) % MOD1 + MOD1) % MOD1;
long long val2 = (aint[1].hash2 - sum2 * (i-m) % MOD2 + MOD2) % MOD2;
if (val1 == hash1 && val2 == hash2)
sol.push_back(i-m+1);
/// sterg i-m+1
update (1,1,n,nrm[v[i-m+1]],0);
}
cout<<sol.size()<<"\n";
for (auto it : sol)
cout<<it<<" ";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |